Mi az a Turing-gép?

Nehéz röviden leírni, matematikai háttere is van, de nagy vonalakban egy olyan elméleti gép, amiben van:

- egy végtelen hosszú mágnesszalag (memória), ami írható és olvasható,

- egy író-olvasó fej, ami a szalag éppen alatta álló celláját el tudja érni,

- egy regiszter, ami a fejből kap vagy oda küld adatot, és ez egyben a gép aktuális állapota.

A gép a szalag soron következő cellájáról képes beolvasni egy adatot, utána:

- visszaír egy másik adatot, vagy

- valamelyik szomszédos cellára mozgatja a szalagot.

Az állapota mindkét esetben megváltozik.

Tulajdonképpen az elemi gépi műveleteket határozza meg. Ezekre az elemi műveletekre lebontható minden véges algoritmus, és egy ilyen géppel futtatható. Ezzel az is vizsgálható, hogy egy problémának létezik-e számítógéppel megoldható algoritmusa.

Ez így elég primitívnek tűnhet, de nagy hatással volt a korai számítógépek tervezésére. Az alapelemek (ha más formában is) még a mai számítógépekben is megtalálhatók.

Egy véges számú állapottal rendelkező (mechanikus) gép, amely papírszalagokra ír vagy olvas az állapotának megfelelően.

mj1: ilyesmi gépek tényleg léteztek [link]

mj2: a te számítógéped is véges számú állapottal rendelkezik, bár nagyon sokkal. (De nincs végtelen szalagja, így "butább" mint egy Turing-gép.)

mj3: ha matematikusok vagy matematikust játszó informatikusok beszélnek róla, akkor halmazzal definiálják, amely halmazban valahogy ott van hogy hány szalagja van, mik az állapotok, milyen állapotok esetén mit csinál. Ez elég nagy szívatásnak tűnhet, de ha átjutsz rajta, akkor látni fogod hogy nem vészes.

mj4: van egy nagyon nagy kiszámíthatósági osztály:

- amit egy Turing-teljes nyelven írt program (végtelen tárral) ki tud számolni (pl Java program)

- amit egy (szabad akarat nélküli) matematikus ki tud számolni

- stb

Mind szimulálni tudják egymást, és ezért ugyanazt tudják kiszámolni. (Lásd itt: [link] ) A Turing gép ennek egy, viszonylag egyszerűen kezelhető eleme.

mj5: A 20-ik század elején már kapargálták a kérdést a matematikusok, hogy mely problémákat lehet megoldani és melyeket nem. A Turing-gép a _legelső_ olyan fizikai modell, amely képes ugyanazokat megoldani, mint egy matematikus. (Turing-gép sem hozható létre fizikailag, mert végtelen/tetszőlegesen hosszú szalagot igényelne, majdnem Turing gép viszont létrehozható, ellentétben Gödel rekurzív függvényeivel (amivel pár évvel korábban megoldotta a kiszámíthatósággal kapcsolatos kérdéseket).)

lásd még:

[link] wiki

[link] Lovász: Algoritmusok bonyolultsága (jegyzet)