Főmenü megnyitása

Módosítások

nincs szerkesztési összefoglaló
[[Fájl:Maquina.png|350px|bélyegkép|jobbra|Egy Turing-gép művészi ábrázolása]]
 
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).
 
A ''Turing-gép'' úgynevezett [[absztrakt automata]]: a valóságos digitális számítógépek nagyon leegyszerűsített [[Modell (tudomány)|modellje]] (részletesebben ld. következő fejezet). További jelentőségét az ún. [[Church–Turing-tézis]] adja, amely szerint univerzális algoritmikus modell (ld. [[#A Church-Turing-tézis|lentebb]]). Az ilyen egyszerű számítógépmodellek matematizált elméleteivel a [[matematika]] [[számítógép-tudomány]]nak nevezett eléggé fiatal tudományágának olyan részterületei foglalkoznak, mint például a [[számításelmélet]].
Az időbeli lefutást leírva a gép beolvas, változtat, mozog, és aztán ez a ciklus újra kezdődik: azon a cellán, amelyre mozgott, ismét beolvas, változtat, majd lép. Így megy ez, s eme folyamatnak a gép programozásától és az elvégzendő feladattól függően kétféle kimenetele lehet:
# '''Szabályos megállás''' ('''terminálás'''): a gép leálló belső állapotba („stop-állapot”) kerül;
# „'''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.
 
== A formális, matematikai modell ==
# <math> \Phi \subseteq \Sigma </math> az elfogadó vagy '''végállapot'''ok halmaza.
 
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>.
 
Nyugodtan feltehető viszont (nem kötelezően, de megszorítást vagy lényegi, matematikai különbséget csak ritkán okoz), és az egyszerűség kedvéért általában fel is szokás tételezni, hogy egyrészt az input ábécé és az output ábécé megegyezik – a Turing gép „'''homogén'''”, mégpedig háromelemű: az „üres szimbólumot”, és mondjuk a 0-t és az 1-et tartalmazza. Az ilyen gépeket '''bináris bemenetű Turing-gép'''eknek nevezzük. Matematikailag ez azt jelenti, hogy <math> \Lambda_{i} = \Lambda_{o} := \Lambda = \{ 0,1, </math> <big> □ </big><math> \} </math>. A legtöbb esetben azonban még célszerűbb a '''bővített bináris bemenetű''' Turing-gépeket vizsgálni: ezek ábécéje a fenti szimbólumokon kívül még egy * „elválasztójelet” is tartalmaz.
=== A gép működésének formális leírása ===
 
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.
 
A formális Turing-gép működésének matematikai lényege, hogy az egyes elemi működési fázisok mindegyikében, a kiinduló fázistól kezdve egészen a végső fázisig (ha van ilyen), a gép egy véges elemrendszerrel jellemezhető, ti. minden fázisban a gép egyértelműen jellemezhető az általunk megadott állapotjellemzőkkel, ezek:
* az aktuális cella tartalma, az aktuális szimbólum;
* az aktuális állapot;
* az előbbi kettő hatására (ti. függvényében) létrejövő output-szimbólum ;
* az első kettő hatására létrejövő címzés;
 
Könnyű azt a formális Turing-gépet és átmenetfüggvényét elkészíteni, amely kettő vagy több egyes számrendszerbeli számot összead a következőképp: a gép szalagjára fel van írva két szám mint egyesek sorozata, úgy, hogy őket néhány * elválasztó szimbólum választja el. A gép „összeadja” ezeket a számokat egyszerűen úgy, hogy „egyesíti” a sorozatokat, kitörölve a köztük lévő elválasztójeleket.
 
Ö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 következő feltevésekkel élünk: a gép leolvasófeje kezdetben mindig a szalagon balról az első nem üres, azaz 1-est tartalmazó cellán álljon, a számokat mindig egy * karakter válassza el, és az utolsó számot az jelzi, hogy utolsó 1-ese után csupa üres szimbólum következik, a legbaloldalibb és legjobboldalibb 1-esek közt pedig csupa egyes vagy * álljon, üres cella ne legyen. Ilyen tehát az input.
 
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>
 
A gép <math> \delta </math> átmenetfüggvényét táblázat alakban ábrázolva:
=== A Turing-algoritmusok megszámlálhatóak és felsorolhatóak ===
 
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)<sup>n×k</sup>. 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<sup>n×(k-1)</sup>. 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!
<!-- Sőt, az ábécén valamilyen [[rendezés]]t értelmezve, ennek segítségével [[lexikografikus rendezés|lexikografikusan rendezhetjük]] az átmenetfüggvény-értékeket mint rendezett elemhármasokat, eme rendezés segítségével pedig magukat az algoritmusokat is (hiszen ezek meg rendezett elem-n×k-asok!). Így adott egy rendezés a megszámlálható sok Turing-gépféleségen, így ezek fel is sorolhatóak. -->
 
=== Formális ekvivalencia ===
 
Két
<center><math> TM_{1} = \left( {\Lambda_{i}}_{1} , {\Lambda_{o}}_{1} , {\Sigma}_{1} , A, s_{1}, \sigma_{1} , u, \delta_{1} , {\Phi}_{1} \right) </math></center>
és
* C, LISP, Java, Prolog, Pascal stb.
 
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.
 
== Történelem ==
=== A múlt… ===
 
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é.
 
A [[második világháború]] táján, több más, [[Alan Turing|Turingtól]] függetlenül dolgozó szerző (például [[Stephen Cole Kleene|S. C. Kleene]], [[Alonzo Church|A. Church]], [[Andrej Andrejevics Markov|A. A. Markov]], [[George H. Mealy|G. H. Mealy]], [[Neumann János]]) is hasonló gondolatok kidolgozásán fáradozott. Máig Turing koncepciója a leginkább kutatott és oktatott, legalapvetőbbnek tekintett algoritmusmodell. A negyvenes években, elektronikai ismeretekkel felvértezve, Turing az elméleti számítógép gyakorlati megvalósításán, a [[Colossus (számítógép)|Colossus]] megtervezésében és építésében munkálkodott, az angol titkosszolgálat kötelékében. Ez időszakban egyébként többen is építettek már számítógépet (az első digitális gépet [[Vincent Atanasoff]] és [[Clifford Berry]], ill. az első programozható digitális gépet Konrad Zuse).
69 449

szerkesztés