Az említett gépek felépítése a következő. Minden gép tartalmaz egy vezérlőegységet, egy programkártyát, és egy adatszalagot. Az adatszalag egy cellákra osztott tároló, amelyen tetszőleges szimbólumok (betűk, számok stb.) lehetnek. Minden cella egy szimbólumot tartalmazhat. A szalag egy író-olvasó fej alatt mozog, amelyik egyszerre mindig csak egy cellát lát. A kiindulási állapotban a szalag teljesen üres.
A programkártya egy táblázat, amely ún. állapotokra oszlik. A vezérlőegység tárolja azt, hogy éppen melyik az aktív állapot. A táblázat első két oszlopa egy állapotot és egy szimbólumot tartalmaz, második két oszlopa pedig egy tevékenységet és a következő állapotot.
A működés nagyon egyszerű. A vezérlőegység megnézi, hogy a szalagon milyen szimbólum található az aktuális pozícióban. Ezután az aktuális állapota és a beolvasott szimbólum alapján kiválasztja a nekik megfelelő sort a táblázatból. (Ezek egyértelműen ki kell jelöljenek egy sort, különben hibás a program.) Végrehajtja az ott megadott tevékenységeket, végül pedig átugrik az utolsó oszlopban adott következő állapotra. És így folytatja a végtelenségig.
| állapot | szimbólum | tevékenység | köv. állapot |
|---|---|---|---|
| start | üres | P0, J | egy |
| egy | üres | P1, J | start |
A fenti példaprogram teleírja a szalagot a 010101… sorozattal. Bekapcsoláskor a gép a
start állapotba kerül. Megvizsgálja a szalagot, ahol egy üres cellát talál (hiszen
bekapcsoláskor a szalag üres). Ez az állapot és szimbólum kombináció kijelöli az első sort. Leír
(P) ezért egy 0-t a gép az aktuális pozícióra, utána pedig jobbra lép (J), és átugrik az
egy állapotba. A következő körben majdnem ugyanez történik: a szalag az új pozíción megint
üres, de most az egy állapotban van a gép. Ezért a második sor alapján leír egy
1-est, és jobbra lép, aztán vissza a start állapotba.
| állapot | szimbólum | tevékenység | köv. állapot |
|---|---|---|---|
| plusz-egy | bármi | - | van-átv |
| nincs-átv | 0 | P0, B | nincs-átv |
| nincs-átv | 1 | P1, B | nincs-átv |
| nincs-átv | üres | B | vége |
| van-átv | 0 | P1, B | nincs-átv |
| van-átv | 1 | P0, B | van-átv |
| van-átv | üres | P1, B | vége |
| vége | bármi | - | vége |
A második példaprogram jóval hosszabb. Ennek feladata megnövelni egy kettes számrendszerben
leírt számot eggyel – feltéve, hogy akkor indítjuk el, amikor a szám legalsó helyiértéke az
aktuális szalagpozíció alatt van, és tőle balra vannak az egyre növekvő helyiértékek. A program
a következőképp működik. Tegyük fel, hogy az előző körből hoztunk átvitelt (van-átv).
Akkor ha 0-t látunk, az 1-re kell változtatni, mert 0+1=1; és a következő körben nem lesz
átvitel. Viszont ha 1-est, akkor 1+1=2 (10kettő), ezért 0-t kell leírni, és a
következő körben is számolni kell az átvitellel. Ha nem hoztunk átvitelt az előző körből
(nincs-átv), akkor egyszerűen le kell másolni az aktuális szimbólumot (0+0=0, 1+0=1),
és ugyanígy folytatni. Ez történik a szám közepén.
Lássuk a szám elejét és végét. Egyrészt, a szám végére, azaz a legnagyobb helyiértéke utáni
első üres cellára érve, hozott átvitel esetén még le kell írni egy 1-est. Ez azt jelenti, hogy a
számjegyek száma megnőtt eggyel. Ha nem hoztunk átvitelt, akkor viszont nincs teendő. Mindkét
esetben a program végeztével a szám utáni első üres cellán fog állni a szalag. Másrészt, a szám
végén, legalsó helyiértéknél (az egyeseknél) is egy kicsit mást kell csinálni, mint a többinél.
Ott elvileg nincsen átvitel az előző körből (nem volt előző kör), de az volt a feladat, hogy
hozzá kell adni egyet a számhoz. Ezért úgy vehetjük, mintha lett volna. Ezzel a trükkel indul az
összeadás. Az induláskor, a plusz-egy állapotban a gép nem csinál semmit, csak
átugrik a van-átv állapotba. Vagyis a legalsó helyiértéket úgy dolgozza fel, mintha
lett volna átvitel az előző körből.
Egy megkonstruált Turing-gép
A Turing-gépek igazából érdemi munkára alkalmatlanok, csak elvi jelentőségük van. A programozásuk nagyon nehéz, nem igazán követi az emberi gondolkodást. A megírt programok pedig lassúak, az idejük nagy részét azzal töltik, hogy ide-oda tekergetik a szalagot, és keresik a különféle módon megjelölt cellákat. Az ehhez hasonlóan viselkedő, minimalista programozási nyelveket „Turing tarpit”-nek szokták nevezni angolul.