„Turing-gép” változatai közötti eltérés

A '''Turing-gép''' fogalmát [[Alan Turing]] [[angolok|angol]] [[matematikus]] dolgozta ki [[1936]]-ban megjelent [[Turing-gép#Történelem|cikkében]] a matematikai számítási [[eljárás]]ok, [[algoritmus]]ok precíz leírására, tágabb értelemben pedig mindenfajta „gépies” problémamegoldó folyamat, például az akkoriban még nem létező [[számítógép]]ek működésének modellezésére. Erre az időszakra, a [[második világháború]] környékére tehető az ilyesfajta, a számítási eljárásokat azok különféle modelljein keresztül vizsgáló kutatások fellendülése, melyek végül a valódi [[számítógép]]ek építésébe torkollottak (Turing maga is részt vett egy valódi gép, a [[Colossus (számítógép)|Colossus]] megépítésében).

# „'''Elszállás'''”: a gép végtelen ideig fut. A legegyszerúbblegegyszerűbb módon ez úgy lehet, hogy egy végtelen ciklusba kerül, de más módon is futhat végtelen ideig, mert egyszerűen sosem kerül stop állapotba.

Kötelezően feltesszük, hogy ha egy felhasznált szimbólum állapotjel, akkor nem lehet tárjel vagy címjel, és viszont, azaz hogy <math> \left[ \left( \Lambda_{i} \cup \Lambda_{o} \right) \cap \Sigma \right] \cup \left[ \left( \Lambda_{i} \cup \Lambda_{o} \right) \cap A \right] \cup \left[ \Sigma \cap A \right] = \empty </math>.

A <math> \delta </math> kétváltozós és háromértékű átmenetfüggvény biztosítja, hogy ha a gép valamely működési fázis elején adott <math> s \in \Sigma </math> állapotban adott <math> x \in \Lambda_{i} </math> szimbólumot olvas be az aktuális cellából, akkor egyértelműen rendelkezésére álljon egy cellacím, egyértelműen kiírhasson egy outputszimbólumot abba cellába, ahová a cím szól, és egyértelműen átválthasson egy másik állapotba, tehát tényleg az átmenetfüggvény vezérli a gépet, hisz ez szabja meg a viselkedését, hogy milyen bemenetre milyen kimenetet ad.

* az előbbi kettő hatására (ti. függvényében) létrejövő output-szimbólum ;

Összeadó algoritmus megvalósítására több konkrét lehetőség is van. Egy ilyen Turing-gépet a következőképp tervezhetünk meg:

A gép a kezdőállapotban (<math> \alpha </math>) megkeresi az első elválasztójelet (*), ha megtalálja, átvált a <math> \beta </math> állapotba, átírja 1-essé, és visszalép a számsorozat első 1-ese előtti üres celláig. Ekkor <math> \gamma </math> állapotba lép, törli az első 1-est. Tehát az egész összeadandó sorozat eddig a legbaloldalibb egyessel csökkent, de közben az első csillag 1-esre változott, így az első két számot összeadtuk. A gép lépjen eggyel jobbra: ott szükségképp 1-est talál. Most majdnem ugyanaz a helyzet, mint kezdetben: az összeadandó számsor legbaloldalibb egyesén állunk, és össze kell adnunk a még összeadandókat (csak két szám már össze van adva, ennyivel közelebb a megoldás). Mivel ez tulajdonképp majdnem megint a kiinduló helyzetünk, „menjük„menjünk vissza alfába”, keressük meg a következő *-ot, ezt „bétában” írjuk felül 1-essel, „gammában” pedig töröljünk egy egyest a számsorozatunk elejéről. Ez a ciklus addig folytatódik, amíg az utolsó csillag el nem fogy: ezt a gép úgy tudja érzékelni, hogy az <math> \alpha </math> állapotban jobbra lépkedve nem csillagba, hanem a sorozat végén lévő üres cellába ütközik. Ekkor váltsunk <math> \omega </math> állapotba, mely a befejezendő állapot. Összeadtuk az összes számot.

Tehát Turing-gépünk, kereszteljük UNAD-1 névre, matematikailag egy <math> UNAD-1 = ( \Lambda_{i} , \Lambda_{0} , \Sigma , A, 1 , </math> □ <math> , \delta , \Phi ) </math> nyolcas, ahol <math> \Lambda_{i} = \Lambda_{o} := \Lambda = \{ 0,1,*,</math> □ <math> , \} </math>, <math> \Sigma = \left\{ \alpha , \beta , \gamma , \delta \right\} </math>, <math> \Phi = \left\{ \omega \right\} </math>

Az előbbi kiszámolt eredményre a következőképp lehet jutni: adott véges n elemű ábécé feletti 1<k-állapotú Turing-gép egyértelműen megadható egy átmenetfüggvénnyel. Ez olyan táblázat, melynek n oszlopa és k sora van, tehát n×k cellája. Minden cellábencellában az átmenetfüggvény egy lehetséges értéke áll, egy elemhármas, mely egy külső, egy belső és egy címszimbólumból álló rendezett elemhármas, ilyen pedig n×k×3 db. van. Mármost bármely cellába elvileg bármely lehetséges elemhármas beírható (persze az így kapott átmenetfüggvények többsége olyan gépet eredményez, ami semmi értelmeset nem csinál, például ha minden kimenő állapot stop-állapot, de bizony ez is egy Turing-gép), tehát n×k×3 elem n×k-adosztályú [[variáció]]járól van szó. Ezek száma pedig (n×k×3)^n×k. A becslés javítható, ha a stop-állapotot nem számítjuk külön sornak (mert ha a gép stop-állapotba kerül, akkor már nem számít ki több átmenetfüggvény-értéket, az stopnak megfelelő táblázatsor üres), az így kapott eredmény n×k×3^n×(k-1). Azért is érdemes ezt részletesen taglalni, mert észre lehet venni mindebből, hogy az adott ábécé feletti izomorf Turing-gépek (ti. ezek osztályai) felsorolhatóak, vagyis adott ábécé felett megszámlálhatóan végtelen sok nem-izomorf (Turing-) algoritmus létezik!

Két

AVAGY a [[Parciálisan rekurzív függvény]] szócikk alatt:

A Church-Turing-tézis, vagy Church-tézis az az állítás, hogy a parciálisan rekurzív függvények pontosan az (algoritmussal) kiszámítható függvények. Ez matematikailag ellenőrizhető állítássá válik, ha az algoritmussal kiszámíthatóság homályos fogalma helyett bármilyen más matematikailag precízen megadott függvényosztályt vizsgálunk, így igazolható például, hogy a parciálisan rekurzív és a Turing-géppel kiszámítható függvények egybeesnek.

Turing [[1936]]-ban dolgozta ki a Turing-gép fogalmát egy cikkében ('''''[http://www.abelard.org/turpap2/tp2-ie.asp On computable numbers, with an application to the Entscheidungsproblem]'''''). Az [[algoritmus]]ok [[matematika]]i leírásán túl, e problémát általánosítva a [[logika]]i és a [[fizika]]i folyamatok, gondolkodás és cselekvés szintézisére törekedett. E célt szolgálta az úgynevezett (egyetemes vagy) '''univerzális Turing-gép''' teóriája. Ekkor merült fel az a máig nagy vitákat kiváltó kérdés, lehet-e hűen szimulálni, modellezni, sőt esetleg reprodukálni [[számítógép]] segítségével az emberi gondolkodást. Ha a gép társzalagja(i) elegendő hosszúságú(ak), bármi kiszámolható; az összes (jól meghatározott) feladat egyetlen (a szükséges programokkal ellátott) géppel. De hogyan rendszerezhetők, milyen szabályok alapján működnek a valóság matematikailag rendkívül nehezen vagy egyáltalán nem modellálható ''(uncomputable)'' szegmensei, például az emberi intuíció? E kérdésekre egy [[1938]]-as esszében ('''''Ordinal Logics''''') próbált választ adni, a későbbiekben viszont soha többé.