Kiszámíthatóságelméletileg a Turing-gép memóriacelláit milyen adattípusokkal indexelhetjük?

"A turing gépnek nincsenek memóriacellái. Ha lennének, akkor sem adattípussal lenne indexelve, hanem halmazokkal. (Az állapotai például azzal vannak.)"

A Turing-gépnek rengetegféle változata van, e szócikk az ún. klasszikus változattal (teljes nevén szalagtáras, egyszalagos, egyfejes, relatív címzésű, három címes, statikus programozású, véges ábécéjű, véges (állapotú) determinisztikus absztrakt automata) foglalkozik. Bizonyított matematikai tételek szerint a többi változat nagy része ekvivalens a klasszikus változattal – legalábbis ama tekintetben, hogy mit tud kiszámolni.

három nagyobb fizikai egységből („hardver”) áll:

egy cellákra osztott végtelenített papírszalag formában létező memóriából (szalagmemória, szalagtár, társzalag); minden cellában a gép által megértett nyelv betűi, azaz a Tár-abc egy-egy betűje van írva;

egy vezérlőegységből, mely a gép programját tartalmazza; a vezérlőegység különböző időpillanatokban különféle belső állapotokban létezhet;

egy író-olvasó fejből (I/O-fej), mely szimbólumokat ír vagy olvas a szalag celláira (ahogy a valóságos számítógépek betűket írnak ki a monitorra vagy a nyomtatóban lévő papírívre).

továbbá egy „szoftveregységből”, ez az átmenettábla, ami vezérli a gép működését, megadva, hogy adott szimbólum beolvasásának hatására adott állapotban mit tegyen: hogyan mozogjon, milyen szimbólumot írjon a tárra, és milyen belső állapotba kerüljön.

Forrás és további részletek : [link]