Turing-kone

In tietojenkäsittelyteoria , eli Turingin kone on teoreettisen toiminnan mekaanisen tiedonkäsittelyn laitteet , kuten tietokone . Tämän mallin suunnitteli Alan Turing vuonna 1936 algoritmin tai "mekaanisen menettelyn" käsitteen tarkan määritelmän antamiseksi . Sitä käytetään edelleen laajalti teoreettisessa tietojenkäsittelytieteessä , erityisesti algoritmisen monimutkaisuuden ja laskettavuuden aloilla .

Alun perin Turingin koneen, joka keksittiin ennen tietokonetta, oli tarkoitus edustaa virtuaalista henkilöä, joka suorittaa tarkkaan määritellyn toimenpiteen, muuttaa äärettömän nauhan laatikoiden sisältöä ja valitsee tämän sisällön lopullisesta symboleista . Toisaalta henkilön on asetettava menettelyn jokaisessa vaiheessa itsensä tiettyyn tilaan rajallisen joukon joukossa. Menettely on muotoiltu alkeisvaiheiden muodossa, kuten: "jos olet tilassa 42 ja etsimäsi solun symboli on" 0 ", korvaa tämä symboli" 1 ": llä, siirry tilaan 17 , ja katso nyt viereistä aukiota oikealla. "

Kirkko teesi pääperiaatetta että laskennallinen ongelma perustuu algoritmeihin menettelystä voidaan ratkaista Turingin koneella. Tämä opinnäytetyö ei ole matemaattinen lausunto, koska se ei tarkoita algoritmisten menettelyjen tarkkaa määrittelyä. Toisaalta on mahdollista määritellä käsite "hyväksyttävä ohjelmointijärjestelmä" ja osoittaa, että tällaisten järjestelmien teho on yhtä suuri kuin Turingin koneiden (ne ovat Turingin täydellisiä ).

Määritelmä

Vaikka sen nimi "kone" voi saada uskomaan päinvastoin, Turingin kone on abstrakti käsite, toisin sanoen matemaattinen esine. Turingin koneessa on seuraavat osat:

Ääretön nauha jaettu peräkkäisiin neliöt. Jokaisessa laatikossa on tietyn äärellisen aakkosen symboli . Aakkoset sisältävät erikoismerkin, jota kutsutaan "tyhjäksi symboliksi" ('0' seuraavissa esimerkeissä), ja yhden tai useamman muun symbolin. Nauhan oletetaan olevan äärettömän pitkä vasemmalle tai oikealle, toisin sanoen koneella on aina oltava riittävä teipin pituus. Katsomme, että nauhan laatikoissa on oletusarvoisesti "valkoinen symboli";
Luku / kirjoituspää , joka voi lukea ja kirjoittaa symbolit nauha, ja siirtyy vasemmalle tai oikealle nauhan;
Tilarekisteri , joka tallentaa nykyisen tilan Turingin kone. Mahdollisten tilojen määrä on aina rajallinen, ja on olemassa erityinen tila, jota kutsutaan "käynnistystilaksi", joka on koneen alkutila ennen sen suorittamista;
Kannetta taulukko , joka kertoo koneen jonka symboli kirjoittamaan nauhaan, miten siirtää toistopaikkaa (esimerkiksi " " varten laatikossa vasemmalla, " " ja laatikko oikealla), ja mikä on uusi. Tila , riippuen nauhalla olevasta symbolista ja koneen nykyisestä tilasta. Jos tietylle lukusymbolin ja nykyisen tilan yhdistelmälle ei ole mitään toimintoa, kone pysähtyy. $\ vasen nuoli$ $\ oikealle$

Muodollinen määritelmä

Turingin koneesta voidaan antaa useita lähellä toisiaan olevia muodollisia määritelmiä. Yksi niistä, suhteellisen yleinen, valitaan täällä. Turingin kone on viisisarja, jossa: ${\ displaystyle (Q, \ Gamma, q_ {0}, \ delta, F)}$

$Q$ on rajallinen joukko tiloja ;
$\Gamma$ on nauhan symbolien toimiva aakkoset , jotka sisältävät tietyn symbolin (kutsutaan tyhjäksi ) , $B$ $B \ sisään \ Gamma$
$q_0$ on alkutila , ; $q_ {0} \ Q: ssa$
$\ delta: Q \ kertaa \ Gamma \ Q \ kertaa \ Gamma \ kertaa \ {\ leftarrow, \ rightarrow \}$ on siirtymätoiminto ;
$F$ on hyväksyvien tilojen (tai lopullisten päätelaitteiden) joukko . $F \ subseteq Q$

Se on malli täydellisestä ja deterministisestä Turingin koneesta; eli on määritelty ja ainutlaatuinen. ${\ displaystyle \ forall q \ Q, \ forall \ gamma \ in \ Gamma, \ delta (q, \ gamma)}$

Nuolet määritelmässä edustavat luku- / kirjoituspään kahta mahdollista liikettä, nimittäin liikettä vasemmalle ja liikettä oikealle. Tämän siirtofunktion merkitys voidaan selittää seuraavasta esimerkistä: tarkoittaa, että jos Turingin kone on tilassa ja se lukee symbolin , se kirjoittaa sen sijaan , menee tilaan ja siirtää sitten soittopäänsä vasemmalle. $\delta$ $\ delta (q_ {1}, x) = (q_ {2}, y, \ vasen nuoli)$ $q_ {1}$ $x$ $y$ $x$ $q_ {2}$

Turingin koneen toiminta on tällöin seuraava: Laskennan jokaisessa vaiheessa kone kehittyy sen tilan mukaan, jossa se on, ja symbolin, joka on merkitty nauhan ruutuun, jossa lukupää sijaitsee. Näitä kahta tietoa käytetään koneen tilan päivittämiseen siirtymistoiminnon avulla. Aluksi tällä hetkellä kone on tilassa , ja nauhan ensimmäinen symboli on ohjelman syöttö. Kone pysähtyy, kun se siirtyy päätetilaan. Laskennan tulos on sitten sana, jonka muodostavat koneen peräkkäin lukemat symbolit. $q_0$

Voimme rajoittaa määritelmän mahdollisten merkintöjen aakkosia . Tällöin on mahdollista työskennellä tarkemmin tällä aakkosella varaamalla tietyt kokonaisen aakkoksen symbolit koneen laskentavaiheisiin. Erityisesti valkoinen symboli ei saa olla osa merkintää, ja se voi siten määrittää jälkimmäisen loppu . $Sigma$ $\Gamma$ $B$

Seuraava esimerkki käyttää hyvin erilaista versiota Turingin koneesta, jossa kone pysähtyy, jos se on päätelaitteessa ja lukee tietyn merkin nauhasta (tässä valkoinen symboli). Toinen alla oleva esimerkki on ensimmäinen historiallinen esimerkki, jonka Turing antoi vuoden 1936 artikkelissaan: se on kone, joka ei pysähdy.

Esimerkkejä

Tuplaa lukumäärä '1'

Seuraavassa Turingin koneessa on aakkoset {'0', '1'}, '0' on "valkoinen symboli". Oletetaan, että valintanauha sisältää sarjan '1' ja luku- / kirjoituspää on aluksi vasemman reunan '1' yläpuolella. Tämän koneen vaikutus kaksinkertaistaa '1': n määrän lisäämällä '0' kahden sarjan väliin. Esimerkiksi "111" tulee "1110111".
Koneen mahdollisten tilojen joukko on {e1, e2, e3, e4, e5} ja alkutila on e1.
Toimintataulukko on seuraava:

Esimerkki siirtymätaulukosta

Vanha valtio	Lue symboli	Kirjallinen symboli	Liike	Uusi valtio
e1	0	(Lopettaa)
e1	1	0	Aivan	e2
e2	1	1	Aivan	e2
e2	0	0	Aivan	e3
e3	1	1	Aivan	e3
e3	0	1	Vasen	e4
e4	1	1	Vasen	e4
e4	0	0	Vasen	e5
e5	1	1	Vasen	e5
e5	0	1	Aivan	e1

Tämän koneen käyttäminen kahden 1-sarjan sarjassa olisi (luku- / kirjoituspään sijainti nauhalla on lihavoitu ja punaisella kirjaimella):

Suoritus (1)

Vaihe	Osavaltio	Nauha
1	e1	1 1
2	e2	0 1
3	e2	01 0
4	e3	010 0

Suoritus (2)

Vaihe	Osavaltio	Nauha
5	e4	01 0 1
6	e5	0 1 01
7	e5	0 101
8	e1	1 1 01

Suoritus (3)

Vaihe	Osavaltio	Nauha
9	e2	10 0 1
10	e3	100 1
11	e3	1001 0
12	e4	100 1 1

Suoritus (4)

Vaihe	Osavaltio	Nauha
13	e4	10 0 11
14	e5	1 0 011
15	e1	11 0 11
	(Lopettaa)

Tämän koneen käyttäytymistä voidaan kuvata silmukaksi:

Se aloittaa suorituksen tilassa e1, korvaa ensimmäisen 1 arvolla 0.
Sitten se käyttää tilaa e2 siirtyäkseen oikealle, ohittaen 1: t (vain yhden tässä esimerkissä), kunnes se kohtaa 0 (tai tyhjän) ja menee tilaan e3.
Tilaa e3 käytetään sitten ohittamaan seuraava sekvenssi 1 (aluksi ei mitään) ja korvaamaan ensimmäiset 0 kohdatut luvulla 1.
Tila e4 antaa mahdollisuuden palata vasemmalle, kunnes löydetään 0, ja vaihtaa tilaan e5.
Tila e5 antaa sitten taas mahdollisuuden siirtyä vasemmalle, kunnes löydetään 0, jonka alun perin on kirjoittanut tila e1.
Sitten kone korvaa tämän 0 arvolla 1, siirtää yhden solun oikealle ja siirtyy jälleen tilaan e1 silmukan uudelle iteraatiolle.

Tätä prosessia toistetaan, kunnes e1 putoaa 0: een (se on keskimmäinen 0 kahden 1: n sekvenssin välillä); tällä hetkellä kone pysähtyy.

Laske kolmasosa binäärinä

Seuraavassa esimerkissä Turingin koneella on tyhjä nauha ja sen avulla voit rakentaa sekvenssin 01010101010101 ...

Esimerkki äärettömästä pöydästä

Vanha valtio	Kirjallinen symboli	Liike	Uusi valtio
Vastaanottaja	0	Aivan	b
b	1	Aivan	Vastaanottaja

Tämän koneen toteutus olisi (nauhan luku- / kirjoituspään sijainti on kirjoitettu lihavoituna ja magentana ):

Äärettömän koneen käyttö

Vaihe	Osavaltio	Nauha
1	Vastaanottaja	0
2	b	0 1
3	Vastaanottaja	01 0
4	b	010 1
5	Vastaanottaja	0101 0
6	b	01010 1
7	Vastaanottaja	010101 0
8	b	0101010 1
...	...	01010101 ...

Tämän koneen käyttäytymistä voidaan kuvata loputtomaksi silmukaksi:

Se aloittaa suorituksen tilassa a, lisää 0 ja liikkuu oikealle.
Sitten se menee tilaan b, lisää 1 ja liikkuu oikealle.
Se palaa tilaan a ja toistaa ensimmäisen vaiheen.

Tämä kone on vastine kolmannen laskennalle, jonka binäärikirjoitus on 0,010101010101 ...

Turingin yleiskoneet

Kuten Alan Turing osoittaa perimmäisessä artikkelissaan, on mahdollista luoda Turingin kone, jota kutsutaan "universaaliksi Turingin koneeksi", joka pystyy "simuloimaan" minkä tahansa muun Turingin koneen käyttäytymistä. "Simuloi" tarkoittaa, että jos yleinen Turingin kone vastaanottaa tulona koneen T ja datan D koodauksen , se tuottaa saman tuloksen kuin kone T , jolle data D annettaisiin syötteenä .

Universaalilla Turingin koneella on kyky laskea mikä tahansa laskettava: sanomme sitten, että se on Turingin täydellinen . Tarjoamalla sille sopivan koodauksen se voi simuloida mitä tahansa rekursiivista toimintoa , analysoida mitä tahansa rekursiivista kieltä ja hyväksyä minkä tahansa osittain ratkaistavan kielen . Mukaan Church-Turingin teesi , ongelmia, jotka voidaan ratkaista universaali Turingin kone on juuri ongelmia, jotka voidaan ratkaista toimesta algoritmin tai jonka konkreettinen laskentamenetelmää .

Turingin koneen toteutus

Turingin kone on ajatuksen kohde: sen nauha on ääretön ja siksi Turingin koneen muisti on ääretön. Turingin kone ei koskaan aiheuta muistin ylivuotoa , toisin kuin tietokone, jonka muisti on rajallinen. Unohtamalla tämä muistiongelma voimme simuloida Turingin konetta modernilla tietokoneella.

On myös mahdollista rakentaa puhtaasti mekaanisia Turing-koneita. Ajatuskohde Turingin kone on siis monistettu useaan otteeseen joskus melko omaperäisillä tekniikoilla, joista tässä on muutamia esimerkkejä:

Sisään huhtikuu 2011, Jim MacArthur valmisti kompaktin mekaanisen 5-symbolisen Turing-koneen, jossa oli kuulalaakerit nauhan tietovälineenä.
Sisään maaliskuu 2012, Turing-vuoden (en) aikana ryhmä opiskelijoita École normale supérieure de Lyonista valmisti kokonaan Lego- osista valmistetun Turing-koneen ilman elektroniikkaa.

Sisään joulukuu 2013, kokeellinen prototyyppi Turingin koneiden toteuttamiseksi (sähkömekaaninen: valmistettu Turingin aikakauden tekniikoilla), pyöreällä nauhalla ja suhteellisen helposti ohjelmoitavalla. Suunniteltu kahteen siirrettävään osaan, sitä voidaan käyttää esityksiin ja oppitunneihin.
Lokakuussa 2020 Thierry Delattren (Dunkirk) suunnittelema opettavainen Turing-kone, joka voidaan ohjelmoida enintään 12 tilan ja kolmen symbolin aakkosille. 50 algoritmia voidaan tallentaa muistiin. Versio, jossa on 22 osavaltiota ja 8 symbolia, on peräisin helmikuusta 2021.

Viitteet ja lähdeluettelo

Viitteet

(in) Harry R. Lewis ja Christos Papadimitriou , Elements of Laskennan teoria . Prentice-Hall , 1982; toinen painos syyskuussa 1997.
"FINAL" , CNRTL: "Itse asiassa finaalien ja finaalien välillä on kellua : 1. s näyttää olevan plur. kielen. tuomioistuin. kirjailijoiden, toinen kielitieteilijöiden ja taloustieteilijöiden ” .
Kévin Perrot, " Laskettavuus. Kurssi 1: Turingin koneet ” , osoitteessa univ-mrs.fr ,kevät 2019(kuultu marraskuussa 2020 )
(sisään) Jim MacArthur, " Turing Machine " , osoitteessa srimech.blogspot.fr ,8. kesäkuuta 2012(käytetty 20. helmikuuta 2018 ) .
" RUBENS- projekti " osoitteessa rubens.ens-lyon.fr ,maaliskuu 2012(käytetty 20. helmikuuta 2018 ) .
David Larousserie, Le Monde , " Täysin mekaaninen kone, josta ei puutu ilmaa " , osoitteessa lemonde.fr ,22. kesäkuuta 2012(käytetty 20. helmikuuta 2018 ) .
Marc Raynaud, “ Ohjelmoitava prototyyppi Turingin koneen toteuttamiseksi ” sivustolla machinedeturing.org ( käyty 19. helmikuuta 2018 ) .
Ouest-France , " Marc Raynaud, oppinut matemaatikko-keksijä " , osoitteessa ouest-france.fr ,14. helmikuuta 2018(käytetty 14. syyskuuta 2020 ) .
" Turing Machine - Koodissa on sitten mielenkiintoisia kevyitä animaatioita, matemaattisia laskelmia binääriluvuille, numerosarjoja tai mitä tahansa muuta sovellusta, jonka voit keksiä vapaasti!" » (Pääsy 19. maaliskuuta 2021 )

Bibliografia

Käyttöohjeet

Olivier Carton, Muodolliset kielet, laskettavuus ja monimutkaisuus: matematiikan tai tietojenkäsittelytieteen kandidaatin ja maisterin tutkinto, matematiikan yhdistämisen tietojenkäsittelytieteen vaihtoehto , Pariisi, Vuibert ,2008, 237 Sivumäärä ( ISBN 978-2-7117-2077-4 , SUDOC 128299258 ) ;
Jean-Michel Autebert, Laskettavuus ja päätettävyys , Pariisi, Masson,1992, 118 Sivumäärä ( ISBN 978-2-225-82632-0 , SUDOC 002676494 ) ;
Éric Jacopin, Les machines de Turing: Johdanto ongelman monimutkaisuuden kuvaamiseen , Toulouse, Éditions Cépaduès ,2009, 264 Sivumäärä ( ISBN 978-2-85428-865-0 , SUDOC 132323214 ) ;

Turing

Alan Turing ja Jean-Yves Girard , La machine de Turing , Pariisi, Éditions du Seuil,1995, 192 Sivumäärä [ painoksen yksityiskohdat ] ( ISBN 9782020369282 ) ; tämä työ sisältää erityisesti alkuperäisen artikkelin käännöksen ranskaksi (Julien Baschin ja Patrice Blanchardin) sekä Emil Postin oikaisun siellä esiintyvistä virheistä;
(en) Alan Turing, ” On Computable Numbers, with an Application to Entscheidungsproblem ”, Proceedings of the London Mathematical Society, Series 2 , voi. 45,1936, s. 230-265 ( lue verkossa ) ;
(fr) Alan Turing, "Computable Numbers" ( lue verkossa ). - Luonnos muistiinpanoksi Pariisin tiedeakatemian julkaisuille.

Kleene

Stephen Cole Kleene , Johdatus metamatematiikkaan , Amsterdam, Pohjois-Hollanti,1952, x + 550 Sivumäärä ( SUDOC 005505526 , online-esitys ) - Lukuisat uusintapainokset vuosina 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009, erityisesti Wolters-Noordhoff (Groningen) ( ISBN 0720421039 ) , Sudoc-ilmoituksen mukaan. Monet käännökset.
(en) , (fr) Stephen Cole Kleene, matemaattinen logiikka , Dover ,1967- Reprint Dover reprint , 2001, ( ISBN 0-486-42533-9 ) . French käännös Jean Largeault , Logique Mathématique , Armand Colin, 1971 ja Gabay 1987 ( ISBN 2-87647-005-5 ) .

: tämän artikkelin lähteenä käytetty asiakirja.

Katso myös

Aiheeseen liittyvät artikkelit

Ei-deterministinen Turingin kone ;
Todennäköinen Turing-kone ;
Vuorotteleva Turing-kone ;
Symmetrinen Turing-kone ;
Blum-Shub-Smale- kone: yleistys koneille, jotka laskevat ; $\ mathbb {R}$
Päätöksen ongelma ;
Ajatuskokeilu ;
Oracle (Turingin kone) ;
Jäljitelmä Game , elokuva elämästä Alan Turing kanssa Benedict Cumberbatch ;
Rakennettava toiminto .

Ulkoiset linkit

Christophe Gombertin ja Hugo Deboisen elokuvan "The Turing Machine Realised" katsottavaksi verkossa ilmaiseksi.
Alan Turing keskeytyy nero : esittely ja bibliografiassa BNF konferenssin , jonka Bernard Chazelle aikataulun mukaan19. maaliskuuta 2014
Hamdi Ben Abdallah, “ Kuinka Turingin kone toimii? », Välikappaleet ,22. maaliskuuta 2013( lue verkossa ), artikkeli, jonka avulla voi kokeilla Turingin konetta.