Turing gép

Az elméleti számítástechnikában a Turing-gép a mechanikus számítástechnikai eszközök , például a számítógép működésének elvont modellje . Ezt a modellt Alan Turing találta ki 1936-ban, hogy pontos meghatározást nyújtson az algoritmus vagy a "mechanikus eljárás" fogalmának . Még mindig széles körben használják az elméleti informatikában , különösen az algoritmikus bonyolultság és a kiszámíthatóság területén .

Eredetileg a Turing gépének a számítógép előtt kitalált koncepciójának egy virtuális személyt kellett volna képviselnie, aki pontosan meghatározott eljárást hajt végre, megváltoztatja a végtelen szalag dobozainak tartalmát, és ezt a tartalmat a szimbólumok véges halmazából választja . Másrészt az eljárás minden szakaszában a személynek egy meghatározott állapotba kell helyeznie magát egy véges halmaz között. Az eljárás olyan alapvető lépésekben van megfogalmazva, mint például: "ha a 42 -es állapotban van, és a keresett cellában lévő szimbólum" 0 ", akkor cserélje le ezt a szimbólumot" 1 "-re, menjen a 17-es állapotba , és most nézze meg a szomszédos négyzetet a jobb oldalon ”.

Az egyházi tézis szerint minden algoritmikus eljáráson alapuló számítási probléma megoldható egy Turing-géppel. Ez a tézis nem matematikai állítás, mivel nem feltételezi az algoritmikus eljárások pontos meghatározását. Másrészről lehetséges meghatározni az „elfogadható programozási rendszer” fogalmát, és bebizonyítani, hogy az ilyen rendszerek ereje megegyezik a Turing-gépekével (ezek Turing-teljesek ).

Meghatározás

Bár a "gép" neve az ellenkezőjét hiheti, a Turing-gép elvont fogalom, vagyis matematikai tárgy. A Turing-gép a következő alkatrészekkel rendelkezik:

Egy végtelen szalagot osztva egymást követő négyzetek. Minden doboz egy adott véges ábécé szimbólumát tartalmazza . Az ábécé tartalmaz egy speciális szimbólumot, amelyet "üres szimbólumnak" neveznek (a következő példákban "0"), és egy vagy több más szimbólumot. Feltételezzük, hogy a szalag végtelen hosszú balra vagy jobbra, más szóval a gépnek mindig elegendő szalaghosszal kell rendelkeznie a futáshoz. Úgy véljük, hogy a szalag dobozai alapértelmezés szerint tartalmazzák a „fehér szimbólumot”;
A író / olvasó fej , hogy tud írni és olvasni szimbólumok a szalagot, és mozog balra vagy jobbra a szalag;
A állami nyilvántartás , amely tárolja az aktuális állapotát a Turing-gép. A lehetséges állapotok száma mindig véges, és van egy speciális állapot, az úgynevezett "indítási állapot", amely a gép kezdeti állapota a végrehajtása előtt;
Az akció táblázat , amely megmutatja a gép melyik szimbólum write a szalagon, hogyan mozog a playhead (például „ ” egy mezőbe balra „ ” egy doboz a jobb oldalon), és mi az új. Állami , a szalagon olvasható szimbólumtól és a gép aktuális állapotától függően. Ha az olvasott szimbólum és az aktuális állapot adott kombinációjára nincs művelet, a gép leáll. $\ bal nyíl$ $\ jobb nyíl$

Formális meghatározás

Számos, egymáshoz közeli formális definíció adható meg egy Turing-gépről. Az egyiket, viszonylag gyakori, itt választják. A Turing-gép ötös, ahol: ${\ displaystyle (Q, \ Gamma, q_ {0}, \ delta, F)}$

$Q$ véges állapothalmaz ;
$\Gamma$ a munka ábécé a szimbólumok a sávot, amely egy adott szimbólum (úgynevezett üres ) ,; $B$ $B \ be \ Gamma$
$q_0$ a kezdeti állapotban , ; $q_ {0} \ Q-ban$
$\ delta: Q \ times \ Gamma \ to Q \ times \ Gamma \ times \ {\ leftarrow, \ rightarrow \}$ az átmeneti függvény ;
$F$ az elfogadó állapotok (vagy végleges terminálok) halmaza . $F \ subseteq Q$

Ez egy komplett és determinista Turing-gép modellje; azaz meghatározott és egyedi. ${\ displaystyle \ forall q \ Q, \ forall \ gamma \ Gamma, \ delta (q, \ gamma)}$

A nyilak a definícióban az olvasási / írási fej két lehetséges mozgását jelentik, nevezetesen balra és jobbra. Ennek az átmeneti függvénynek a jelentése a következő példán magyarázható: azt jelenti, hogy ha a Turing-gép állapotban van, és elolvassa a szimbólumot , akkor az helyett ír , az állapotba megy , majd a lejátszófejét balra mozgatja. $\delta$ $\ delta (q_ {1}, x) = (q_ {2}, y, \ balra nyíl)$ $q_ {1}$ $x$ $y$ $x$ $q_ {2}$

A Turing-gép működése ekkor a következő: a számítás minden szakaszában a gép annak az állapotnak megfelelően alakul, amelyben megtalálható, és a szimbólum be van írva a szalag azon mezőjébe, ahol az olvasófej található. Ez a két információ a gép állapotának frissítésére szolgál az átmeneti funkció segítségével. A kezdeti pillanatban a gép állapotban van , és a szalag első szimbóluma a program beírása. A gép leáll, amikor terminál állapotba lép. A számítás eredménye ezután a gép által egymás után olvasott szimbólumok által képzett szó. $q_0$

Szűkíthetjük a definíció lehetséges bejegyzéseinek ábécéjét . Így pontosabban lehet ezen az ábécén dolgozni, ha a teljes ábécé bizonyos szimbólumait lefoglalja a gép számítási lépései számára. Különösen a fehér szimbólum nem lehet a bejegyzés része, ezért meghatározhatja az utóbbi végét . $\ Sigma$ $\Gamma$ $B$

Az alábbi első példa a Turing-gép egy kissé eltérő változatát használja, amelyben egy gép leáll, ha terminál állapotban van, és felolvas egy bizonyos karaktert a szalagon (itt a fehér szimbólum). Az alábbi második példa az első történelmi példa, amelyet Turing adott 1936-os cikkében: ez egy olyan gép, amely nem áll le.

Példák

Az „1” számának duplázása

A következő Turing-gépnek van egy ábécéje: '' 0 ',' 1 '},' 0 'a "fehér szimbólum". Tegyük fel, hogy a szalag '1' sorozatát tartalmazza, és az olvasási / írási fej kezdetben a bal szélső '1' fölött van. Ennek a gépnek az a hatása, hogy megduplázza az „1” számát, ha a „0” -t szúrja be a két sorozat közé. Például a "111" "1110111" lesz.
A gép lehetséges állapotainak halmaza: {e1, e2, e3, e4, e5}, a kezdeti állapot pedig e1.
A cselekvési táblázat a következő:

Példa egy átmeneti táblára

Régi állapot	Olvassa el a szimbólumot	Írásbeli szimbólum	Mozgalom	Új állam
e1	0	(Állj meg)
e1	1	0	Jobb	e2
e2	1	1	Jobb	e2
e2	0	0	Jobb	e3
e3	1	1	Jobb	e3
e3	0	1	Bal	e4
e4	1	1	Bal	e4
e4	0	0	Bal	e5
e5	1	1	Bal	e5
e5	0	1	Jobb	e1

A gép két '1-es sorozatának futtatása lenne (az olvasási / írási fej pozíciója a szalagon vastag és piros betűkkel van megírva):

Végrehajtás (1)

Színpad	Állapot	Szalag
1	e1	1 1
2	e2	0 1
3	e2	01 0
4	e3	010 0

Végrehajtás (2)

Színpad	Állapot	Szalag
5.	e4	01 0 1
6.	e5	0 1 01
7	e5	0 101
8.	e1	1 1 01

Végrehajtás (3)

Színpad	Állapot	Szalag
9.	e2	10 0 1
10.	e3	100 1
11.	e3	1001 0
12.	e4	100 1 1

Végrehajtás (4)

Színpad	Állapot	Szalag
13.	e4	10 0 11
14	e5	1 0 011
15	e1	11 0 11
	(Állj meg)

A gép viselkedése hurokként írható le:

Az e1 állapotban kezdi meg a végrehajtását, az első 1-et 0-val helyettesíti.
Ezután az e2 állapot segítségével mozog jobbra, kihagyva az 1-eket (ebben a példában csak egyet), amíg 0-val (vagy üresen) nem találkozik, és e3 állapotba kerül.
Az e3 állapotot használjuk az 1-es (kezdetben egyik sem) következő szekvenciájának kihagyására és az első 0-val való helyettesítésére 1-vel.
Az e4 állapot lehetővé teszi a balra való visszatérést, amíg egy 0 nem található, és az e5 állapotra váltást.
Az e5 állapot ezután ismét lehetővé teszi a balra haladást, amíg egy 0-t nem találunk, amelyet eredetileg az e1 állapot írt.
Ezután a gép ezt a 0-t 1-gyel helyettesíti, egy cellát jobbra mozgat és ismét átmegy az e1 állapotba a hurok új iterációjához.

Ezt a folyamatot addig ismételjük, amíg e1 0-ra nem esik (ez a középső 0 az 1 két szekvenciája között); ilyenkor a gép leáll.

Számítson egy harmadot bináris formában

A következő példában a Turing-gép üres szalaggal rendelkezik, és lehetővé teszi a 01010101010101 ...

Példa egy végtelen táblára

Régi állapot	Írásbeli szimbólum	Mozgalom	Új állam
Nak nek	0	Jobb	b
b	1	Jobb	Nak nek

Ennek a gépnek a végrehajtása a következő lenne (az olvasási / írási fej pozíciója a szalagon félkövér és bíborvörös karakterekkel van megírva ):

A Végtelen gép működtetése

Színpad	Állapot	Szalag
1	Nak nek	0
2	b	0 1
3	Nak nek	01 0
4	b	010 1
5.	Nak nek	0101 0
6.	b	01010 1
7	Nak nek	010101 0
8.	b	0101010 1
...	...	01010101 ...

Ennek a gépnek a viselkedése végtelen ciklusként írható le:

Az a állapotban kezdi el végrehajtani, hozzáad egy 0-t és jobbra mozog.
Ezután b állapotba kerül, hozzáad egy 1-et és jobbra mozog.
Visszatér az a állapotba és megismétli az első lépést.

Ez a gép egy harmadik számításának megfelelője, amelynek bináris írása 0,010101010101 ...

Univerzális Turing gépek

Amint Alan Turing alapvető cikkében bemutatja, lehetséges létrehozni egy "univerzális Turing-gépnek" nevezett Turing-gépet, amely képes "szimulálni" bármely más Turing-gép viselkedését. A "szimuláció" azt jelenti, hogy ha az univerzális Turing-gép bemenetként megkapja a T gép kódját és a D adatokat , ugyanazt az eredményt adja, mint a T gép , amelyhez a D adatokat bemenetként adnák .

Egy univerzális Turing-gép képes kiszámolni bármit, ami kiszámítható: akkor azt mondjuk, hogy Turing-teljes . Megfelelő kódolással biztosítva szimulálhat bármilyen rekurzív függvényt , elemezhet bármilyen rekurzív nyelvet és elfogadhat bármilyen részben eldönthető nyelvet . A Church-Turing tézis szerint az univerzális Turing-géppel megoldható problémák pontosan azok a problémák, amelyeket algoritmussal vagy konkrét számítási módszerrel lehet megoldani .

Turing-gép megvalósítása

A Turing-gép gondolkodás tárgya: szalagja végtelen, ezért a Turing-gép memóriája végtelen. Egy Turing-gép soha nem generál túlcsorduló memóriát , ellentétben azzal a számítógéppel, amelynek memóriája véges. Ha megfeledkezünk erről a memóriaproblémáról, szimulálhatunk egy Turing-gépet egy modern számítógépen.

Lehetséges tisztán mechanikus Turing-gépek gyártása is. A Turing-gép, egy tárgy a gondolat, ezért arra megtestesítettük számos alkalommal technikákat alkalmaznak, amelyek néha egészen eredeti, amelyből itt néhány példa:

Ban ben 2011. április, Jim MacArthur készített egy kompakt, 5 szimbólumú Turing-gépet golyóscsapágyakkal, mint a szalag információhordozóját.
Ban ben 2012. március, a Turing-év (en) alkalmából az École normale supérieure de Lyon diákjainak csapata teljesen Lego alkatrészekből gyártott Turing-gépet gyártott elektronika nélkül.

Ban ben 2013. december, egy kísérleti prototípus a Turing-gépek valóra váltásához (elektro-mechanikus: a Turing-korszak technológiáival készült), kör alakú szalaggal és viszonylag könnyen programozhatóval. Két szállítható részből áll, előadásokhoz és órákhoz használható.
2020 októberében egy Thierry Delattre (Dunkirk) által tervezett oktatási Turing-gép, amely maximum 12 állapotú algoritmusokhoz programozható, és három szimbólumból áll. 50 algoritmus tárolható a memóriában. A 22 állammal és 8 szimbólummal ellátott változat 2021 februárjától származik.

Hivatkozások és irodalomjegyzék

Hivatkozások

(in) Harry R. Lewis és Christos Papadimitriou , elemei elmélet számítási . Prentice-Hall , 1982; második kiadás 1997. szeptember.
„végső” , CNRTL: „Tény, hogy lebeg között döntők és döntők : a 1 st úgy tűnik, hogy a plur. a lang. bíróság. írók, a második a nyelvészek és a közgazdászoké ” .
Kévin Perrot, „ Számíthatóság. 1. tanfolyam: Turing-gépek ” , az univ-mrs.fr oldalon ,2019 tavasza(konzultáció: 2020 novemberében )
(in) Jim MacArthur " Turing-gép " , a srimech.blogspot.fr ,2012. június 8(megtekintve : 2018. február 20. ) .
" RUBENS Project " , a rubens.ens-lyon.fr webhelyen ,2012. március(megtekintve : 2018. február 20. ) .
David Larousserie, Le Monde , " Teljesen mechanikus gép, amelyből nem hiányzik a levegő " , a lemonde.fr oldalon ,2012. június 22(megtekintve : 2018. február 20. ) .
Marc Raynaud, „ Programozható prototípus a Turing-gép megvalósításához ” a machinedeturing.org oldalon (hozzáférés : 2018. február 19. ) .
Ouest-France , " Marc Raynaud, tanult matematikus feltaláló " , az ouest-france.fr oldalon ,2018. február 14(megtekintés : 2020. szeptember 14. ) .
" Turing Machine - A kód akkor vonzó könnyű animációkat, matematikai számításokat tartalmaz bináris számokra, számsorokra vagy bármilyen más alkalmazást, amelyet szabadidejében kitalálhat!" » (Hozzáférés : 2021. március 19. )

Bibliográfia

Kézikönyvek

Olivier Carton, Hivatalos nyelvek, kiszámíthatóság és összetettség: matematika vagy informatika alap- és mesterképzés, matematika összesítésének informatikai lehetősége , Párizs, Vuibert ,2008, 237 o. ( ISBN 978-2-7117-2077-4 , SUDOC 128299258 ) ;
Jean-Michel Autebert, kiszámíthatóság és határozhatóság , Párizs, Masson,1992, 118 p. ( ISBN 978-2-225-82632-0 , SUDOC 002676494 ) ;
Éric Jacopin, Les machines de Turing: Bevezetés a probléma összetettségének jellemzésébe , Toulouse, Éditions Cépaduès ,2009, 264 p. ( ISBN 978-2-85428-865-0 , SUDOC 132323214 ) ;

Turing

Alan Turing és Jean-Yves Girard , La Machine de Turing , Párizs, Éditions du Seuil,1995, 192 o. [ kiadás részlete ] ( ISBN 9782020369282 ) ; ez a munka magában foglalja különösen az eredeti cikk francia nyelvű fordítását (Julien Basch és Patrice Blanchard), valamint Emil Post javítását az ott megjelenő hibákról;
(en) Alan Turing, „ A kiszámítható számokról, egy alkalmazással az Entscheidungsproblemhez ”, Proceedings of the London Mathematical Society, Series 2 , vol. 45,1936, P. 230–265 ( online olvasás ) ;
(fr) Alan Turing, a „Számolható számok” ( online olvasható ). - Jegyzet tervezete a Párizsi Tudományos Akadémia kiadványaihoz.

Kleene

Stephen Cole Kleene , Bevezetés a metamatematikába , Amszterdam, Észak-Hollandia,1952, x + 550 p. ( SUDOC 005505526 , online előadás ) - Számos újranyomás, 1957-ben, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009, különösképpen Wolters-Noordhoff (Groningen) ( ISBN 0720421039 ) szerint, a Sudoc-közlemény szerint. Sok fordítás.
(en) , (fr) Stephen Cole Kleene, matematikai logika , Dover ,1967- Reprint Dover reprint, 2001, ( ISBN 0-486-42533-9 ) . Jean Largeault , Logique mathématique , Armand Colin, 1971 és Gabay 1987 francia fordítása ( ISBN 2-87647-005-5 ) .

: a cikk forrásaként használt dokumentum.

Lásd is

Kapcsolódó cikkek

Nem determinisztikus Turing-gép ;
Valószínűségi Turing-gép ;
Váltakozó Turing-gép ;
Szimmetrikus Turing-gép ;
Blum-Shub-Smale gép: általánosítás a gépekre, amelyek kalkulálnak ; $\ mathbb {R}$
A döntés problémája ;
Gondolatkísérlet ;
Oracle (Turing-gép) ;
Utánzó játék , film Alan Turing életéről Benedict Cumberbatch- szel ;
Beépíthető funkció .

Külső linkek

Christophe Gombert és Hugo Deboise "A Turing-gép megvalósult" című filmet online ingyen nézhető meg.
Alan Turing megszakított zseni : bemutatás és az irodalomjegyzék a BNF konferencia által Bernard CHAZELLE , ütemezett2014. március 19
Hamdi Ben Abdallah: „ Hogyan működik egy Turing-gép? », Interstices ,2013. március 22( online olvasás ), egy cikk, amely lehetővé teszi egy Turing-gép kipróbálását.