Jego definicja pewnej maszyny Turinga wyglądała następująco: Maszyna operuje na dwustronnej nieskończonej (czy inaczej mówiąc nieograniczonej) taśmie. Funkcja zmiany stanu maszyny posiada 2 wejścia: bieżący stan maszyny oraz znak pod bieżącą pozycją taśmy produkuje 3 wyniki: znak do zapisania nad miejscem wczytanym (może to być ten sam znak co został wczytany); kierunek ruchu (w lewo lub prawo -- „żaden” nie jest dopuszczalne w tym modelu) i stan, do którego ma przejść (może to być ten sam stan lub stan zatrzymania). Tak więc jest to maszyna Turinga tego rodzaju, że jej „program” składa się z tablicy krotek 5-elementowych o postaci (bieżący stan, bieżący znak, znak do zapisania, kierunek przesunięcia, następny stan). Maszyna zatrzymuje się zawsze, gdy osiągnie stan Stop.
Zacznijmy z czystą taśmą (tzn. każde miejsce na taśmie zawiera 0). Zapuszczamy maszynę (stosując raz po razie funkcję przejścia).