Tjuringova mašina

Tjuringova mašina je apstraktna "mašina" koja manipuliše simbole na polju trake prema tabeli pravila; tačnije, to je matematički model koji definiše takav uređaj. Uprkos jednostavnosti modela, bilo koji računarski algoritam, Tjuringova mašina može biti konstruisana tako da je u stanju da simulira logiku tog algoritma.

Mašina radi na beskrajnoj traci memorije podeljenoj u ćelije. Mašina pozicionira svoju glavu iznad ćelije i "čita" (skenira) simbol tamo. Zatim po simbolu i njegovom sadašnjem mestu u konačnoj tabeli korisničkih navedenih uputstva mašina (i) piše simbol (npr cifre ili pismo od konačnog alfabeta) u ćeliji (neki modeli omogućavaju brisanje simbola i / ili ne pisanje), zatim (ii) ili pomera jednu ćeliju trake levo ili desno (neki modeli omogućavaju nepokretnost, pojedini modeli pomeraju glavu), zatim (iii) (kako je utvrđeno u posmatranom simbolu i mestu u tabeli mašine) ili nastavlja s narednim uputstvom ili zaustavlja računanje.

Tjuringovu mašinu je izumeo 1936. godine Alan Tjuring, koju je nazvao A-mašina (automatska mašina). Sa ovim modelom Tjuring je bio u stanju da odgovori na dva pitanja u negativnom: (1) Da li postoji mašina koja može da utvrdi da li je bilo koja proizvoljna mašina na svom snimku "kružna" (npr .zamrzne ili da ne nastavi svoj računarski zadatak); Slično tome, (2) ne postoji mašina koja može da utvrdi da li će bilo koja proizvoljna mašina na svom snimku ikada štampati dati simbol. Tako pružajući matematički opis vrlo jednostavnog uređaja proizvoljnim izračunavanjem, bio je u stanju da dokaže svojstva računanja uopšte - i posebno, neizračunljivosti Hilbertovog Entscheidungsproblem ("Problem odluka").

Tako, Tjuringove mašine dokazuju osnovna ograničenja na snazi mehaničkog izračunavanja. Dok oni mogu izraziti proizvoljne proračune, njihov minimalistički dizajn ih čini nepodobnim za obračun u praksi: stvarni računari su zasnovani na različitim dizajnima koji, za razliku od Tjuring mašine, koriste RAM (memorija).

Tjuringova potpunost je sposobnost za sistem instrukcija da simuliraju Tjuringovu mašinu. Programski jezik koji je Tjuring potpun teoretski je u stanju da izrazi sve zadatke ostvariv računarima; skoro svi programski jezici su Tjuring potpuni.

Pregled

Tjuringova mašina je opšti primer procesora koji kontroliše sve manipulacije podacima koje obavlja kompjuter. Tačnije, to je mašina (automat) sposobna da nabraja neke proizvoljne podskupove važećih stringova alfabeta; ovi nizovi su deo seta rekurzivnog nabrajanja.

Pod pretpostavkom crne kutije, Tjuringova mašina ne može znati da li će na kraju nabrajati svaki posebno niz podskupova sa datim programom. To je zbog činjenice da je halting problem nerešiv, koji ima velike implikacije za teorijske granice računarstva.

Tjuringova mašina je u stanju da obradi gramatiku bez ograničenja, što dodatno podrazumeva da je u stanju da snažno vrednuje logiku prvog reda beskonačnim brojem načina. Ovo je slavno pokazano kroz lambda račun.

Tjuringova mašina koja je sposobna da simulira bilo koju drugu Tjuring Mašinu se zove univerzalna Tjuringova mašina (UTM, ili jednostavno univerzalna mašina). Mnogo više matematički orijentisana definicija sa sličnom "univerzalnom" prirodom je uveo Alonzo Čerč, čiji se rad na lambda računu prepliće sa Tjuringovim u formalnoj teoriji računanja koja je poznata kao Čurč-Tjuringova teza. Teza navodi da Tjuringove mašine zaista uhvate neformalni pojam efikasnih metoda u logici i matematici, i daju preciznu definiciju algoritma ili "mehaničkog postupka". Studiranje svojih apstraktnih osobina daje mnogo uvida u informatiku i teorije kompleksnosti.

Fizički opis

U svom eseju 1948. godine, "Inteligentna mašina", Tjuring je napisao da je njegova mašina koja se sastoji od: ... neograničen kapacitet memorije dobijene u obliku beskonačne trake obeležene kvadratima, i na svakom simbol može biti odštampan. U svakom trenutku postoji jedan simbol u mašini; to se zove skeniran simbol. Mašina može menjati skenirane simbole, a njegovo ponašanje delimično određuje taj simbol, ali simboli na traci na drugom mestu ne utiču na ponašanje mašine. Međutim, traka može da se pomera napred i nazad kroz mašinu, što je jedna od osnovnih operacija mašine. Bilo koji simbol na traci može, dakle, na kraju imati učešće. (Tjuring (1948). str. 3)

Neformalni opis

Tjuringova mašina matematički modelira mašinu koja mehanički radi na traci. Na ovoj traci su simboli koji mašina može da čita i piše, jedan po jedan, koristeći glavu trake. Operacija je u potpunosti određena konačnim skupom osnovnih instrukcija, kao što su "u stanju 42, ako je simbol video 0, napiši 1, a ako je simbol video 1, promenite u stanje 17; u stanju 17, ako je simbol video 0, napišite 1 i promeniti u stanje 6; "itd. Originalnog članka ("na izračunljivim brojevima, sa primenom Entscheidungsproblem", vidi reference ispod), Tjuring nije zamišljao mehanizam, ali osoba koga je nazvao "kompjuter", koji sprovodi ova deterministička mehanička pravila ropski (ili kako Tjuring kaže, "u nepovezanom načinu").

Ovde je unutrašnje stanje (q1) prikazano u glavi, i ilustracija opisuje traku kao da je beskonačna i napunjena sa "0", simbol služi kao prazno. Sistemski puno stanje (njena potpuna konfiguracija) se sastoji od unutrašnjeg stanja, bilo koji ne prazni simboli na traci (u ovoj ilustraciji "11B"), kao i položaja glave u odnosu nad tim simbolima, uključujući praznine, odnosno "011B". (Pisanje posle Minskog (1967) p. 121).

Preciznije, Tjuringova mašina se sastoji od:

Imajte na umu da svaki deo mašine (tj svoje stanje, kolekcije simbola, i upotrebljene trake u svakom trenutku) i njegove akcije (kao što su štampanje, brisanje i kretanja trake) su konačna, diskretna i različita; to je neograničena količina trake i izdržljivost koja mu daje neograničenu količinu skladišnog prostora.

Formalna definicija

Nakon Hopkrofta i Ulmana ( (1979). str. 148), (jedna traka) Tjuringove mašine može biti formalno definisana kao sedmorka M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle

$Q$ je konačan, neprazan skup stanja
$\Gamma$ je konačan, neprazan skup traka simbola alfabeta
$b\in \Gamma$ je prazan simbol (jedini simbol dozvoljen da se javi na traci beskonačno često na svakom koraku tokom izračunavanja)
$\Sigma \subseteq \Gamma \setminus \{b\}$ je skup ulaznih simbola
$\delta :(Q\setminus F)\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ je delimična funkcija zvana funkcija tranzicije, gde je L leva promena, R desna promena. (Relativno retka varijanta omogućava "nema pomak", kaže N, kao treći element drugog seta.) Ako \delta nije definisan na trenutnom stanju i trenutnom simbolu trake, onda mašina zastaje.
$q_{0}\in Q$ je početno stanje
$F\subseteq Q$ je skup krajnjih ili prihvatanja stanja. Ulazni sadržaj trake je rekao da bude prihvaćen od strane M ako se na kraju zaustavio na stanju iz F.

Sve što radi po ovim specifikacijama je Tjuringova mašina.

Sedmorka za 3-stanja zauzetog dabra izgleda ovako (videti više o zauzetosti dabra na primerima Tjuringovr mašine):

$Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}$
$\Gamma =\{0,1\}$
$b=0$ ("prazno")
$\Sigma =\{1\}$
$q_{0}={\mbox{A}}$ (ulazno stanje)
$F=\{{\mbox{HALT}}\}$
$\delta =$ viđeno stanje-tabela ispod

Tabela stanja za 3 stanja, 2 simbola zauzetog dabra
Simbol trake	Trenutno stanje A			Trenutno stanje B			Trenutno stanje C
Simbol trake	Simbol koji se piše	Pomeranje trake	Sledeće stanje	Simbol koji se piše	Pomeranje trake	Sledeće stanje	Simbol koji se piše	Pomeranje trake	Sledeće stanje
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	HALT

Dodatni detalji potrebni za vizuelizaciju ili da se sprovedu Tjuringove mašine

Prema rečima van Emde Boasa (1990). str. 6: "Skup-teorijski predmet [njegov formalni opis sedmorke sličan gore] daje samo delimične informacije o tome kako će se mašina ponašati i kako će njegovi proračuni izgledati."

Na primer,

Tamo mora biti mnogih odluka o tome kako simboli zapravo izgledaju, i uspešno dokazan način čitanja i pisanja simbola unedogled.
Pomak levo i pomak desno operacije mogu pomeriti glavu traku preko trake, ali zapravo kada se pravi Tjuringova Mašina praktičnije je napraviti traku slajd napred i nazad ispod glave umjesto toga.
Traka može biti konačna, i automatski produžena sa prazninama po potrebi (koji je najbliži matematičkoj definiciji), ali je češće da mislimo o tome kao beskonačno istezanje na oba kraja i biti napunjen sa prazninama, osim ako je na eksplicitno dato konačnom odlomku glava trake na njemu. (Ovo je, naravno, neizvršivo u praksi.) Traka ne može biti fiksirana u dužini, sve dok to ne bi odgovaralo datoj definiciji i ozbiljno ograničiti opseg izračunavanja mašine može obavljati sa onima koji su linearno ograničen automat.

Alternativne definicije

Definicije u literaturi se ponekad malo razlikuju, prave argumente ili dokaze lakšim ili jasnijim, ali to se uvek radi na takav način da rezultujuća mašina ima iste računarske moći. Na primer, promena skupa \{L,R\} u \{L,R,N\}, gde bi N bilo ("Nijedan" ili "Nema operacije") dozvoljavaju mašini da ostane na istoj ćeliji trake umesto da se pomera levo ili desno, ne povećavaju računarske moći mašine.

Najčešća konvencija predstavlja svaku "Tjuringovu instrukciju" u "Tjuringovu tabelu" jedna od devet petorki, po konvenciji Tjuring/ Dejvis (Tjuring (1936) u Neodlučivo. str. 126-127 i Dejvis (2000) str . 152):

(definicija 1): (q_i, S_j, S_k/E/N, L/R/N, q_m)

( trenutno stanje q_i , skeniran simbol S_j , odštampaj simbol S_k/izbriši E/nijedan N , pomeri_traku_na_kvadrat_levo L/desno R/nijedno N , novo stanje q_m )

Drugi autori (Minski (1967). str. 119., Hopkroft i Ulman (1979). str. 158., Stoun (1972). str. 9.) donose drugačiju konvenciju, sa novim stanjem q_m navedenim odmah nakon skeniranog simbola S_j:

(definicija 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

( trenutno stanje q_i , skeniran simbol S_j , novo stanje q_m , odštampaj simbol S_k/izbriši E/nijedno N , pomeri_traku_na_kvadrat_levo L/desno R/nijedno N )

Za ostatak ovog člana "definicije 1" (Tjuring / Dejvis konvencija) će se koristiti.

Primer: tabela stanja za 3-stanja 2-simbola zauzetog dabra smanjena na petorku
Trenutno stanje	Skeniran simbol	Odštampaj simbol	Pomeri traku	Završno (tj. sledeće) stanje	Petorka
A	0	1	R	B	(A, 0, 1, R, B)
A	1	1	L	C	(A, 1, 1, L, C)
B	0	1	L	A	(B, 0, 1, L, A)
B	1	1	R	B	(B, 1, 1, R, B)
C	0	1	L	B	(C, 0, 1, L, B)
C	1	1	N	H	(C, 1, 1, N, H)

U sledećoj tabeli, Tjuringov originalni model je dozvolio samo prve tri linije koje je nazvao N1, N2, N3 ( Tjuring u Neodlučivo. str. 126). On je dozvolio brisanje "skeniranog kvadrata" od imenovanja nulto mesto simbolom S0 = "brisanje" ili "prazno", itd. Međutim, nije dozvolio za ne-štampanje, tako da svaka linija instrukcije uključuje "simbol za štampanje Sk" ili "brisanje" (vidi fusnotu 12 u poruci (1947), Neodlučivo pp. 300). Skraćenice su Tjuringove (Neodlučivo pp. 119). Nakon Tjuringovog originalnog rada u 1936-1937, modeli mašina su dozvolili svih devet mogućih vrsta petorki:

Trenutna m konfiguracija (Tjuringovo stanje)	Simbol trake	Operacija - Štampanje	Pomeranje trake	Roditelj m-konfiguracije (Tjuringovo stanje)	Petorka	Komentari petorke	Četvorke
N1	q_i	S_j	Štampaj(S_k)	Levo L	q_m	(q_i, S_j, S_k, L, q_m)	"Prazno" = S₀, 1=S₁, etc.
N2	q_i	S_j	Štampaj(S_k)	Desno R	q_m	(q_i, S_j, S_k, R, q_m)	"Prazno" = S₀, 1=S₁, etc.
N3	q_i	S_j	Štampaj(S_k)	Nijedno N	q_m	(q_i, S_j, S_k, N, q_m)	"Prazno" = S₀, 1=S₁, etc.	(q_i, S_j, S_k, q_m)
4	q_i	S_j	Nijedno N	Levo L	q_m	(q_i, S_j, N, L, q_m)	(q_i, S_j, L, q_m)
5	q_i	S_j	Nijedno N	Desno R	q_m	(q_i, S_j, N, R, q_m)	(q_i, S_j, R, q_m)
6	q_i	S_j	Nijedno N	Nijedno N	q_m	(q_i, S_j, N, N, q_m)	Direkto "Skoči"	(q_i, S_j, N, q_m)
7	q_i	S_j	Izbriši	Levo L	q_m	(q_i, S_j, E, L, q_m)
8	q_i	S_j	Izbriši	Desno R	q_m	(q_i, S_j, E, R, q_m)
9	q_i	S_j	Izbriši	Nijedno N	q_m	(q_i, S_j, E, N, q_m)	(q_i, S_j, E, q_m)

Bilo koja Tjuringova tabela (lista instrukcija) se može konstruisati od gore navedenih devet petorki. Iz tehničkih razloga, tri ne-štampa ili "N" instrukcije (4, 5, 6) mogu se obično izostaviti. Za primere pogledajte primere Tjuringove mašine.

Manje češća upotreba četvorki su naišle: one predstavljaju još jedno raspršivanje Tjuringovih instrukcija (Poruka (1947), Bulos i Džefri (1974, 1999), Dejvis-Sigal-Vijuker (1994)); Vidi još više u Post-Tjuringovoj mašini.

Stanje

Reč "stanje" korišćena u kontekstu Tjuringovih mašina može biti izvor zabune, jer to može da znači dve stvari. Većina komentatora posle Tjuringa su koristili "stanje" da označe naziv / oznaku trenutne instrukcije koje će obavljati-tj sadržaj registra stanja. Ali Tjuring (1936) je napravio jaku razliku između zapisa onoga što je on nazvao mašinska"M-konfiguracija", (njegovo unutrašnje stanje) i mašine (ili osobe) "napredak stanja" kroz obračun - trenutno stanje ukupnog sistema. Šta je Tjuring nazvao "formula stanja" uključuje i trenutna uputstva i sve simbole na traci:

Ranije u svom radu Tjuring je ovo nosio još dalje: on daje primer gde je smešten simbol aktuelne "M-konfiguracije" -oznaka instrukcije-ispod skeniranog kvadrata, zajedno sa svim simbolima na traci (Neodlučivo. str. 121); ovo on naziva "potpuna konfiguracija" (Neodlučivo. str. 118.). Za štampanje "potpune konfiguracije" na jednoj liniji, on stavlja oznaku stanja / M-konfiguracije sa leve strane skeniranog simbola.

Varijanta ovog se vidi kod Klina (1952), gde Stefan Klin pokazuje kako napisati Gudelov broj "situacija" mašina: on stavlja "M-konfiguracijski" simbol q4 otprilike u centru preko skeniranog kvadrata 6 ne- praznih kvadrata na traci (vidi figure Tjuringove-trake u ovom članku) i stavlja ga desno od skeniranog kvadrata. Ali Klin kod sebe odnosi "q4" kao "stanje mašine" (Klin. str. 374-375). Hopkroft i Ulman zovu ovaj "trenutni opis" složenim i prate Tjuringovu konvenciju stavljanja "trenutnog stanja" (oznaka uputstva, M-konfiguracija) sa leve strane skeniranog simbola ( pp. 149).

Primer: ukupno stanje 3 stanja 2 simbola zauzetog dabra nakon 3 „pomeranja (uzeto iz primera „pokreni iz figure ispod):

1A1

To znači: nakon tri poteza traka ima ... 000110000.. na njoj, glava skenira krajnje desno 1, a država je A. Praznine (u ovom slučaju zastupa "0" s) mogu biti deo od ukupnog stanja kao što je prikazano ovde: V01; traka ima jednu 1 na njoj, ali glava skenira 0 ("prazan") do njene leve i stanje je V.

"Stanje" u kontekstu Tjuringove mašine treba da se razjasni kako bi se što se opisuje: (i) trenutna instrukcija, ili (ii) spisak simbola na traci zajedno sa trenutnom instrukcijom, ili (iii) spisak simbola na traci, zajedno sa trenutnim uputstvom postavljenim sa leve strane skeniranog simbola ili sa desne strane skeniranog simbola.

Tjuringov biograf Endru Hudžis (1983: 107) je primetio i opisao ovu konfuziju.

Dijagrami stanja Tjuringove mašine

Tabla za 3 stanja zauzetog dabra (R = štampaj/ispiši a „1)
Simbol trake	Trenutno stanje A			Trenutno stanje B			Trenutno stanje C
Ispiši simbol	Pomeri traku	Sledeće stanje	Ispiši simbol	Pomeri traku	Sledeće stanje	Ispiši simbol	Pomeri traku	Sledeće stanje
0	P	R	B	P	L	A	P	L	B
1	P	L	C	P	R	B	P	R	ZAUSTAVI

"3-stanja zauzetog dabra" Tjuringove mašine u konačnom automatu. Svaki krug predstavlja "stanje" tabele-"M-konfiguracija" ili "instrukcija". "Pravac" tranzicije stanja je prikazan strelicom. Oznaka (npr. 0/P,R) u blizini odlaznog stanja (na "repu" strelice) specificira skenirani simbol koji izaziva određenu tranziciju (npr 0) praćeno /, praćen naknadnim "ponašanjem "mašine, na primer, "R Štampa" pomerite traku "R Desno". Bez generalnog prihvatanja formatu postoji. Konvencija je pokazana posle MakKluskija (1965), Buta (1967), Hila i Petersona (1974).

Sa desne strane: gornjoj tabeli što je izraženo kao " tranzicija stanja" dijagrama.

Obično velike tabele je bolje ostaviti kao tabele (But pp. 74). One su lakše simulirane računaru u obliku tabele (But. str. 74). Međutim, određeni pojmovi-npr. mašine sa "Resetom" stanja i mašine sa obrascima koji se ponavljaju (Hil i Piterson pp. 244ff) Mogu biti lakše viđene kada se posmatraju kao crtež.

Da li crtež predstavlja poboljšanje u svojim tabelama mora da odluči čitač za određeni kontekst. Pogledajte konačni automat za više.

Čitalac bi trebalo da ponovo bude upozoren da takvi dijagrami predstavljaju snimak njihove tabele zamrznute u vremenu, a ne kurs ("putanja") nekog računanja kroz vreme i / ili prostora. Dok svaki put zauzeta dabar mašina "radi" uvek sledi istu putanju stanja, to nije istina za "kopiju" mašine koje mogu biti pružene sa promenljivim ulaznim „parametrima ".

Dijagram "Napredak u oračunanju" pokazuje 3-stanja zauzetog dabra "stanje" (uputstvo) napredak kroz svoje računanje od početka do kraja. Na krajnjem desnom je Tjuringova "potpuna konfiguracija" (Klin "situacija", Hopkroft-Ulman "trenutni opis") na svakom koraku. Ako je mašina trebalo da bude zaustavljena i razjašnjena praznini kako "registar stanja" i cela traka, ove"konfiguracije" mogu da se koriste za ponovno računanje bilo gde u njenom napretku (Tjuring (1936) Neodlučivo pp. 139–140).

Modeli ekvivalentni modelu Tjuringove mašine

Mnoge mašine koje misle da bi mogle da imaju više računarskog kapaciteta nego jednostavna univerzalna Tjuringova mašina može da se pokaže da nema više snage (Hopkroft i Ulman pp. 159 , Minski (1967)). One možda mogu da izračunaju brže, zavisi, ili koristiti manje memorije, ili njihov skup instrukcija može biti manji, ali ne mogu snažnije računati (tj više matematičkih funkcija). (Podsetimo se da je Čurč-Tjuringova teza hipotezira da je ovo istina za bilo koju vrstu mašine: da sve što se može "izračunati" može se izračunati nekom Tjuringovom mašinom.)

Tjuringova mašina ekvivalentna je potisnom automatu koji je napravljen fleksibilnije i konciznije opuštajući poslednji-u-prvi-napolje uslov njenog steka.

Na drugom kraju, neki vrlo jednostavni modeli će se ispostaviti da su Tjuring-ekvivalentni, odnosno da ima istu računsku snagu kao model Tjuringove mašine .

Uobičajeni ekvivalentni modeli su Tjuringova mašina sa više traka, višekanalna Tjuringova mašina, mašine sa ulazom i izlazom, i nedeterministička Tjuringova mašina (NDTM) za razliku od determinističke Tjuringove mašine (DTM) za koje na tabeli akcija ima najviše jedan ulaz za svaku kombinaciju simbola i države.

Samo čita, Desno pokretajuće Tjuringove mašine ekvivalentne su NDKA (kao DKA konverzijom koristeći algoritam NDKA u DKA konverzije).

Iz praktičnih i didaktičkih namera ekvivalent registar mašine može da se koristi kao uobičajen programski jezik.

Izbor c-mašine, proročke o-mašine

Rano u svom radu (1936) Tjuring čini razliku između "automatske mašine" -je "pokret ... potpuno zavisi od konfiguracije" i "izbora mašine":

...čiji je zahtev samo delimično određen konfiguracijom ... Kada takva mašina dostigne jedan od tih dvosmislenih konfiguracija, ne može nastaviti dok neki proizvoljan izbor ne bude učinjen od strane spoljnog operatera. To bi bio slučaj da smo koristili mašine da se bave aksiomatskih sistemima.
— Neodlučivo . str. 118

Tjuring (1936) ne razrađuje, osim u fusnoti u kojoj on opisuje kako se koristi a-mašina za "pronalazak svih dokazivih formula na [Hilbert] računu", a ne koristiti mašinu izbora. On "Pretpostavlja da su izbori uvek između dve mogućnosti 0 i 1. Svaki dokaz će biti utvrđen nizom izbora i₁, i₂, ..., i_n (i₁ = 0 ili 1, i₂ = 0 ili 1, ..., i_n = 0 ili 1), a samim tim i broja 2ⁿ + i₁2^n-1 + i₂2^n-2 + ... +i_n u potpunosti određuje dokaz. Automatska mašina obavlja sukcesivno dokaz 1, dokaz 2, dokaz 3, ... "(Fusnota‡, Neodlučivo, str. 138)

Ovo je zaista tehnika kojim deterministička (npr a) Tjuringova mašina može da se koristi da oponaša dejstvo jedne nedeterminističke Tjuringove mašine; Tjuring je rešio stvar u fusnoti i čini se da ga otpušta iz daljeg razmatranja.

Proročka mašina ili o-mašina je Tjuringova A-mašina koja pauzira svoj proračun na stanju "o" neko vreme, da završi svoju kalkulaciju, da "čeka odluku" o "proroku" - neodređenog entiteta "osim rekavši da ne može biti mašina "(Tjuring (1939). str. 166-168 Neodlučivo). Koncept je sada aktivno u upotrebi matematičara.

Univerzalne Tjuringove mašine

Implementacija Tjuringove mašine

Kao što je Tjuring napisao u Neodlučivo, str. 128 (iskošenost dodata):

Moguće je da se izmisli jedna mašina koja se može koristiti za računanje bilo koje izračunljive sekvence. Ako se ova mašina 'U' isporučuje sa trakom na početku od kojih je napisan na niz torki odvojene zarezom neke kompjuterske mašine 'M' , zatim će 'U' izračunati istu sekvencu kao 'M'

Ovaj nalaz se sada uzima zdravo za gotovo, ali u to vreme (1936) smatrana je zapanjujućim. Model računanja koji je Tjuring nazvao svojom "univerzalnom mašinom" - "U" za kratko smatrana od strane nekih (Dejvis (2000)) da su osnovni teorijski proboj koji je doveo do pojma skladištenog -računarskog programa.

Tjuringov rad sadrži, u suštini, izum modernog računara i neke od tehnika programiranja koji ga prate.
— Minski (1967). str. 104

U pogledu računarske kompleksnosti, univerzalna Tjuringova mašina sa više traka mora biti samo sporija od logaritamskog faktora u odnosu na mašinama koje simulira. Ovaj rezultat je dobijen 1966. godine od strane Hejnija i R. E. Sternsa. (Arora i Barak, 2009, teorema 1.9)

Poređenja sa drugim stvarnim mašinama

Realizacija Tjuringove mašine u LEGO-u

Često se kaže da su Tjuringove mašine, za razliku od jednostavnijih automata, moćne kao prave mašine, i da su u stanju da izvrše bilo operaciju koju pravi program može. Ono što je zanemareno u ovoj izjavi je da, zbog toga što prava mašina može imati samo konačan broj konfiguracija, ova "pravi mašina" nije ništa drugo do linearno ograničen automat. S druge strane, Tjuringove mašine su ekvivalentne mašinama koje imaju neograničen iznos skladišnog prostora za svoje proračune. Međutim, Tjuringove mašine nisu namenjene za modeliranje računara, već su namenjene za modeliranje samog računanja. Istorijski, kompjuteri, koji računaju samo na njihovoj (fiksnoj) internoj memoriji, razvijeni su tek kasnije.

Postoje nekoliko načina da se objasni zašto su Tjuringove mašine koristan model realnih računara:

Sve što pravi računar može da izračuna, Tjuringova mašina može da izračuna. Na primer: " Tjuringova mašina može da simulira bilo koju vrstu potprograma nađenog u programskim jezicima, uključujući rekurzivne procedure i neke od poznatih parametara-prolazu mehanizama" (Hopkroft i Ulman pp. 157). Dovoljno veliki KA može modelovati bilo koji stvarni računar, bez obzira na IO. Dakle, izjava o ograničenjima Tjuringovih mašina će se primenjivati i na stvarnim računarima.
Razlika je samo u sposobnosti Tjuringove mašine da manipuliše se neograničenom količinom podataka. Međutim, s obzirom konačnim iznosom vremena, Tjuringova mašina (kao prava mašina) može manipulisati konačnom količinom podataka.
Kao Tjuringova mašina, prava mašina može imati svoj skladišni prostor proširen po potrebi, kupovinom više diskova ili drugih medija za skladištenje. Ako je snabdevanje ovih staza kratko, Tjuringova mašina može postati manje korisna kao model. Ali, činjenica je da ni Tjuringove mašine, ni prave mašine ne trebaju astronomske iznose skladišnog prostora u cilju obavljanja korisnog računanja. Potrebno vreme za obradu je obično mnogo veći problem.
Opisi programa prave mašine koji koriste jednostavniji apstraktni modeli su često mnogo složeniji nego opisi koristeći Tjuringove mašine. Na primer, Tjuringova mašina opisuje algoritam može imati nekoliko stotina stanja, dok je ekvivalentni deterministički konačni automat (DKA) na datoj realnoj mašini ima kvadrilion. To čini reprezentaciju DKA neizvodljivom da se analizira.
Tjuringove mašine opisuju algoritme nezavisne od koliko memorije koriste. Postoji ograničenje u memoriji u posedu bilo koje trenutne mašine, ali ovo ograničenje može proizvoljno porasti na vreme. Tjuringove mašine omogućavaju nam da dajemo izjave o algoritama koji će (teoretski) zauvek, bez obzira na napredak u konvencionalnoj računarskoj arhitekturi mašine.
Tjuringove mašine pojednostavljuju izjavu algoritama. Algoritmi koji rade na Tjuringovim-ekvivalentnim apstraktnim mašinama su obično više opšte nego njihove kolege koje rade na stvarnim mašinama, jer oni imaju proizvoljno precizne tipove podataka dostupne i nikada nećete morati da se bave sa neočekivanim uslovima (uključujući, ali ne ograničavajući se na, ponestajanje memorije) .

Jedan od načina na koji su Tjuringove mašine siromašni modeli za programe je da se mnogi stvarni programi, kao što su operativni sistemi i procesor teksta, pisani da dobiju neograničen ulaz tokom vremena, i stoga ne zaustave. Tjuringove mašine ne modeliraju takav tok obračuna (ali i dalje mogu da modeluju delove, kao što su pojedine procedure).

Eksperimentalni prototip da se postigne Tjuringova mašina

Ograničenja Tjuringovih mašina

Računarska teorija kompleksnosti

Dalje informacije: Teorija kompleksnosti

Ograničenje Tjuringovih mašina je da ne modeliraju prednosti određenog aranžmana dobro. Na primer, moderni kompjuteri skladištenog-programa su zapravo instance više specifičnog oblika apstraktne mašine poznatu kao slučajni pristup uskladištenog programa mašini ili RASP modela mašina. Kao Univerzalna Tjuringova mašina na kom RASP skladišti svoj "program" u "Memoriji" spolja do "uputstva" svojih konačnih stanja mašine. Za razliku od univerzalne Tjuringove mašine, RASP ima beskonačan broj različitih, numerisanih ali neograničenih "registara" memorijskih "ćelija" koje mogu da sadrže bilo koji broj (vidi Elgot i Robinson (1964), Hartmanis (1971), a posebno Kuk -Rečov (1973); reference u RAM). Raspova mašina sa konačnim stanjima je opremljena sa mogućnošću za indirektno adresiranje (npr sadržaj jednog registra može da se koristi kao adresa da se navede još jedan registar); tako "program" RASP-a može adresovati bilo koji registar u Registarskoj-sekvenci. Posledica ove razlike je da postoje računarske optimizacije koje mogu da se obavljaju na osnovu memorije indeksa, koje nisu moguće u opštoj Tjuringovoj mašini; Tako, kada se Tjuringove mašine koriste kao osnova za skakutavo vreme koje teče, A 'lažna donja granica' može da se dokaže na vremenu koje teče određenih algoritama "(zbog lažnih pojednostavljuje se pretpostavka Tjuringove mašine). Primer za to je binarna pretraga, algoritam koji može da se pokaže da obavlja brže kada se koristi RASP model izračunavanja nego model Tjuringove mašine.

Konkurentnost

Drugo ograničenje Tjuringovih mašina je da one ne modeluju dobro konkurenciju. Na primer, postoji granica veličine celog broj koji se može izračunati od strane uvek-zaustavljajuće nedeterminističke Tjuringove mašine počevši na praznoj traci. (Videti tekst o neograničenom nondeterminizmu.) Nasuprot tome, postoje uvek zaustavljajući istovremeni sistemi bez ulaza koji mogu izračunati ceo broj od neograničene veličine. (Proces može biti kreiran sa lokalnim skladištenjem koji je inicijalizovan sa tačkom od 0 koji istovremeno sebi šalje kako zaustaviti i pokrenuti poruku. Kada primi Idi poruku, ona povećava svoje brojanje od 1 i šalje sebi idi poruku. Kada ona dobija stop poruku, ona prestaje sa neograničenim brojem u svom lokalnom skladištenju.)

Istorija

Ona je opisana 1936 od strane Alana Tjuringa

Istorijska pozadina: računske mašine

Robin Gandi (1919—1995) student Alana Tjuringa (1912—1954) i njegov doživotni prijatelj-prati poreklo pojma "računarska mašina" nazad do Bebidža (oko 1834) i zapravo predlaže "Bebidžovu tezu":

Čitav razvoj i operacije su sada sposobne da se izgube zbog mašinerije.
— (iskošeno gde je Bebidž citiran od strane Gandija. str. 54)

Gandijeva analiza Bebidžove Analitičke mašine opisuje sledećih pet operacija (vidi pp. 52–53.):

Aritmetičke funkcije +, −, × gde − ukazuje "pravilno" oduzimanje x − y = 0 ako je y ≥ x
Bilo koji redosled operacija je operacija
Iteracija operacije (ponavlja n puta operacija R)
Uslovna iteracija (ponavljanje n puta na operaciji R uslovljeno "uspehom" testa T)
Uslovni prenos (tj uslovni "Idi").

Gandi navodi da "funkcije koje se mogu izračunati (1), (2), i (4) su upravo one koji su Tjuring izračunljive". ( pp. 53). On navodi i druge predloge za "Univerzijadu računskih mašina", uključujući one od Persi Ludžet (1909), Leonardo Tores Aj Kuevedo (1914), Mauris d'Okan (1922), Luis Kofignal (1933), Vanevar Buš (1936), Hauvard Ajken (1937). Međutim:

... naglasak je na programiranje fiksnog nepromenjen redosleda aritmetičke operacije. Osnovni značaj uslovnog ponavljanja i uslovnog transfera za opštu teoriju računskih mašina nije prepoznat...
— Gandi pp. 55

Entscheidungsproblem ("problem odluke"): Hilbertovo deseto pitanje 1900-e

Što se tiče Hilbertovih problema koje je postavio čuveni matematičar David Hilbert 1900. godine, jedan aspekt problema # 10 je plutao oko 30 godina pre nego što je upravo uramljen. Hilbertov originalni izraz za # 10 glasi:

Do 1922. godine, ovaj pojam "Entscheidungsproblem" je razvio malo, i H. Behman je izjavio da

Do 1928. godine međunarodnog kongresa matematičara, Hilbert "je napravio njegova pitanja sasvim precizno. Prvo, da li je matematika potpuna ... Drugo, da li je matematika u skladu ... I treće, da li je matematika odlučiva?" (Hudžis pp. 91, Hoking pp. 1121). Prva dva pitanja su odgovorili 1930. Kurt Gedel na istom sastanku na kojem Hilbert je održao govor za odlazak u penziju (mnogo na žalost Hilberta); treće-Entscheidungsproblem je morao da čeka do sredine 1930-ih.

Entscheidungsproblem je da je odgovor prvo tražio preciznu definiciju "definitivnog opštevažećeg recepta", koje Prinston profesor Alonzo Čerč će doći da pozove "efektivnu predvidivost", a 1928. godine takva definicija nije postojala. Ali u narednih 6-7 godina Emil Post je razvio definiciju kretanja radnika od sobe do sobe pisanja i brisanja oznaka po spisku uputstva (Post 1936), kao i Čurč i njegova dva učenika Stiven Klin i J. B. Roser upotrebom Lambda-računa Crkve i Gedelove teorije rekurzije (1934). Čurčov rad (objavljen 15. april 1936) je pokazao da je Entscheidungsproblem zaista "neodlučiv" i tukli su Tjuringa skoro godinu dana (Tjuringov rad podnet 28. maja 1936, objavljen januara 1937). U međuvremenu, Emil Post je podneo kratak rad u jesen 1936. godine, tako da je Tjuring barem imao prednost nad Postom. Dok je Čurč sudio Tjuringov rad, Tjuring je imao vremena da prouči rad Čurča i doda Dodatak gde je skicirao dokaz koji bi Čurčov Lambda-račun i njegova mašina izračunala iste funkcije.

I Post je samo predložio definiciju predvidivosti i kritikovao Čurčovu "definiciju", ali nije dokazao ništa.

Tjuringova (automatska) mašina

U proleće 1935. godine, Tjuring je kao mladi master student na Kraljevskom koledžu Kembridžu, Velika Britanija, prihvatio izazov ; on je bio podstaknut predavanjima logičara M. H. A. Njumana "i naučio iz njih Gedelov rad i Entscheidungsproblem ... Njuman koristi reč 'mehanički' ... U svojoj čitulji Tjuringu 1955 Njuman piše:

Gandi navodi da:

Dok je Gandi verovao da je Njumanova izjava iznad "pogrešna", ovo mišljenje ne dele svi. Tjuring je imao doživotnu zainteresovanost za mašine: "Alan je sanjao da izmišlja pisaće mašine kao dečak; [njegova majka] gospođa Tjuring je imala pisaću mašinu i on je dobro mogao započeti pitajući se šta je značilo zvanjem pisaće mašine 'mehaničkom'" (Hudžis pp. 96). Dok je na Prinstonu doktorirao, Tjuring je sagradio Bulovu logiku-multiplikator (vidi dole). Njegova doktorska teza, pod nazivom "Sistemi logike na osnovu rednih brojeva ", sadrži sledeću definiciju "izračunljive funkcije":

EntscheidungsproblemKada se Tjuring vratio u Veliku Britaniju odmah je postao zajednički odgovoran za razbijanje nemačkih tajnih kodova stvorenih za šifrovanje mašina pod nazivom "Enigma"; On je takođe postao uključen u dizajnu ARM (Automatska Računska Mašina), "[Tjuringov] ARM-predlog je bio efikasno samostalan, a njeni koreni ne leže u EDVACu[američka inicijativa], ali u svojoj univerzalnoj mašini" (Hudžis p. 318). Argumenti i dalje nastavljaju u vezi sa poreklom i prirodom onoga što je imenovano od strane Klina (1952) kao Tjuringova teza. Ali šta je Tjuring dokazao sa svojim modelom računarske-mašine se pojavljuje u njegovom radu izračunljivih brojeva, sa zahtevom za Entscheidungsproblem (1937):

Tjuringov primer (njegov drugi dokaz): Ako je neko pitao za opšte procedure da nam kaže: "Da li to mašina uvek štampa 0", pitanje je "neodlučivog".

1937–1970: „Digitalni računar", rođenje "informatike"

Godine 1937, dok na Prinstonu radi na doktorskoj disertaciji, Tjuring je sagradio digitalni (Bulova logika) multiplikator od nule, praveći lično svoje elektromehaničke releje (Hudžis. str. 138). „Alanov zadatak je bio da otelotvoruje logičan dizajn Tjuringove mašine u mreži releja pogonom prekidača ..." (Hudžis pp. 138). Dok je Tjuring možda bio samo u početku radoznao i eksperimentisao, sasvim iskreni-rad u istom pravcu ide u Nemačku (Konrad Cuze(1938)), i u Sjedinjene Američke Države (Hauvard Aiken) i Džordž Štibic (1937); plodovi njihovog rada su korišćeni od strane Aksisa i savezničke vojske u Drugom svetskom ratu (Hudžis pp. 298–299). U ranim do sredine 1950-ih Hao Vang i Marvin Minski smanjili su Tjuringovu mašinu u jednostavnijem obliku (preteča post-Tjuringove mašine Martin Dejvis); istovremeno evropski istraživači su smanjili moderan elektronski računar do računara kao teorijskog objekta ekvivalentom onome što se sada naziva "Tjuringova mašina". U kasnim 1950-im i ranim 1960-im slučajni paralelni razvoji Melzaka i Lambeka (1961), Minskog (1961), i Šeperdsona i Sturdžisa (1961) sprovode evropske poslove dalje i smanjuju Tjuringovu Mašinu do više prijateljske, računarski nalik apstraktni model nazvan Brojač mašina; Elgot i Robinson (1964), Hartmanis (1971), Kuk i Rekov (1973) obavljaju ovaj posao dalje sa registrom mašine i modela RAM-a - ali u u osnovi svega su samo Tjuringova mašina sa više traka sa aritmetičkim- nalik skupu- instrukcija .

1970–danas: Tjuringova mašina kao model za računanje

Danas, brojač, registrujte se i sa slučajnim pristupom mašine i njihovom gospodaru Tjuringova mašina nastavlja biti model izbora za teoretičare koji istražuju pitanja u teoriji računanja. Posebno, proračunska teorija kompleksnosti koristi Tjuringova mašina:

Kantorovic (2005) Švedska je bila prva da pokaže najjednostavnije očigledne zastupljenosti Tjuringovih mašina objavljeno akademski koji objedinjuje Tjuringove mašine sa matematičkim analizama i analognim računarima.

Primer

Tjuringova mašina ima vrlo jednostavnu konstrukciju. Sastoji se od beskonačne trake, koja ima na sebi kućice u koje mogu da se upisuju simboli, i glave koja može da čita i piše simbole. Za Tjuringovu mašinu se definiše azbuka simbola koja će se u njoj koristiti, i spisak stanja u kojima glava za čitanje i pisanje može da se nalazi. Definišu se početno stanje (S₁), i završno stanje (S_k); početno stanje je stanje u kome se mašina nalazi na početku rada, a kada mašina dođe u završno stanje, prestaje sa radom. Glava može da se pomera za jedno polje ulevo (L), za jedno polje udesno (D), ili da ostane u mestu (M). U zavisnosti od stanja u kome se glava nalazi, i od simbola koji se nalazi u kućici iznad koje je glava postavljena, glava će u tu kućicu upisati određeni simbol, pomeriti se levo ili desno (ili ostati u mestu), i promeniti svoje stanje. Ovaj proces se ponavlja dok Tjuringova mašina ne stigne u završno stanje. Sledi primer Tjuringove mašine koja sabira dva broja:

Azbuka nad kojom Tjuringova mašina radi je sledeća: „1“ (cifra broja), „+“ (znak za sabiranje) „α“ (prazne kućice)

Mašina treba da od niza 1^m+1ⁿ napravi niz 1^m+n. Na primer, od niza ..αα1111+111αα.. treba da napravi niz ..αα1111111αα..

Stanja mašine su:
- S₁ 1 -> α S₂ D - ako je glava u stanju 1, i nalazi se nad poljem u kome je upisano 1, u to polje se upisuje α, glava se pomera desno, i prelazi u stanje 2
- S₂ 1 -> 1 S₂ D - ako je glava u stanju 2, i nalazi se nad poljem u kome je upisano 1, u to polje se upisuje 1, glava se pomera udesno, i ostaje u stanju 2
- S₂ + -> 1 S₃ L - ako je glava u stanju 2, i nalazi se nad poljem u kome je upisano +, u to polje se upisuje 1, glava se pomera ulevo, i prelazi u stanje 3
- S₃ 1 -> 1 S₃ L - ako je glava u stanju 3, i nalazi se nad poljem u kome je upisano 1, u to polje se upisuje 1, glava se pomera ulevo, i ostaje u stanju 3
- S₃ α -> α S_k D - ako je glava u stanju 3, i nalazi se nad poljem u kome je upisano α, u to polje se upisuje α, glava se pomera udesno, i prelazi u završno stanje, k

Komentar: Mašina polazi iz stanja 1, a glava se nalazi nad poljem gde je prva cifra prvog sabirka. Ona tu prvu „1“ briše (upisuje „α“), i zatim se pomera desno sve dok ne naiđe na znak „+“. Umesto znaka plus, upisuje se „1“, i time se dva broja spajaju u jedan. Zatim se glava pomera levo, sve dok ne naiđe na „α“, onda se vraća za jedno polje desno (kako bi bila na početku novog broja), i tu se rad završava. Ovo vraćanje na početak nije bilo neophodno.

Vidi još

Napomene

Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.
Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".
Sipser 2006:137 "A Turing machine can do everything that a real computer can do".
cf Sipser 2002:137. Also Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".
cf Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.
The word used by e.g. Davis 2000:151
This table represents an algorithm or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.
Boolos Burgess and Jeffrey 2002:25
Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.
"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in The Undecidable 1967:119); this notion was added in the 1950s; see more at Halting problem.

Andrew Hodges (2012). Alan Turing: The Enigma - Centenary Edition. Princeton University Press. ISBN 978-0-691-15564-7. .
The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a mechanical process which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf Hodges 1983:129).

See footnote in Davis 2000:151.
Turing 1936 in The Undecidable 1965:132-134; Turing's definition of "circular" is found on pp. 119.
Turing 1936 in The Undecidable 1965:145
Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."
See the definition of "innings" on Wiktionary
A.M. Turing (1948). "Intelligent Machinery (manuscript)". The Turing Archive. str. 3.
Occasionally called an action table or transition function
Usually quintuples [5-tuples]: qiaj→qi1aj1dk, but sometimes quadruples [4-tuples].
pp. 149; in particular, Hopcroft and Ullman assume that \delta is undefined on all states from F

Literatura

Hazewinkel, Michiel, ur. (2001). Encyclopedia of Mathematics. Springer. ISBN 978-1-55608-010-4.

Zoran Ognjanović, Nenad Krdžavac, Uvod u teorijsko računarstvo, FON, Beograd, 2004.

Primarna literatura, izdanja i kompilacije

B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK. ISBN 978-0-19-825079-1.. Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's convention", and Donald W. Davies' Corrections to Turing's Universal Computing Machine
Martin Davis (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY.
Emil Post (1936), "Finite Combinatory Processes—Formulation 1", Journal of Symbolic Logic, 1, 103–105, 1936. Reprinted in The Undecidable pp. 289ff.
Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic, vol. 12. str. 1–11. Reprinted in The Undecidable pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's first and second proofs.
Turing, A. M. (1937). „On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society. s2-42 (1): 230—265. S2CID 73712. doi:10.1112/plms/s2-42.1.230.
Turing, A. M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”. Proceedings of the London Mathematical Society. 43 (6): 544—6. doi:10.1112/plms/s2-43.6.544.
TURING, A. M. (1996). „Intelligent Machinery, A Heretical Theory”. Philosophia Mathematica. 4 (3): 256—260. doi:10.1093/philmat/4.3.256.
F. C. Hennie; R. E. Stearns. (1966). „Two-tape simulation of multitape Turing machines”. JACM. 13 (4): 533—546.

Teorija izračunljivosti

Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic (3rd izd.). Cambridge UK: Cambridge University Press. ISBN 978-0-521-20402-6.
Boolos, George; Burgess, John; Jeffrey, Richard (2002). Computability and Logic (4th izd.). Cambridge UK: Cambridge University Press. ISBN 978-0-521-00758-0.
Taylor L. Booth (1967), Sequential Machines and Automata Theory, John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX Turing Machines includes some recursion theory.
Martin Davis (1958). Computability and Unsolvability. . McGraw-Hill Book Company, Inc, New York.. On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
1Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd izd.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
Hennie, Fredrick (1977). Introduction to Computability. . Addison–Wesley, Reading, Mass. QA248.5H4 1977.. On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'.
Hopcroft, John; Ullman, Jeffrey (1979). Introduction to Automata Theory, Languages, and Computation. Reading Mass: Addison–Wesley. ISBN 978-0-201-02988-8.
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (2nd izd.). Reading Mass: Addison–Wesley. ISBN 978-0-201-44124-6.
Stephen Kleene (1952), Introduction to Metamathematics, North–Holland Publishing Company, Amsterdam Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII Computable functions is on Turing machine proofs of computability of recursive functions, etc.
Knuth, Donald E. (1973). Volume 1/Fundamental Algorithms: The Art of computer Programming (2nd ed.). Reading, Mass.: Addison–Wesley Publishing Company.. With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 History and Bibliography pp. 225ff and 2.6 History and Bibliography pp. 456ff.
Manna, Zohar (2003) [1974]. Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0.
Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.
Papadimitriou, Christos (1993). „Turing machines”. Computational Complexity. (1st ed.). Addison Wesley. str. 19—56. ISBN 978-0-201-53082-7.
Hartley Rogers, Jr. (1967). Theory of Recursive Functions and Effective Computability. The MIT Press. Cambridge MA, paperback edition 1987, original McGraw-Hill edition. ISBN 978-0-262-68052-3.
Sipser, Michael (1997). „The Church–Turing Thesis”. Introduction to the Theory of Computation. PWS Publishing. str. 125–149. ISBN 978-0-534-94728-6.
Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures. New York: McGraw–Hill Book Company. ISBN 978-0-07-061726-1.
Peter van Emde Boas 1990, Machine Models and Simulations. str. 3–66, in Jan van Leeuwen, ed., Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, [place?]. ISBN 978-0-444-88071-0. (Volume A). QA76.H279 1990. Valuable survey, with 141 references.

Čerčova teza

Dershowitz, Nachum; Gurevich, Yuri (11. 9. 2008). „A Natural Axiomatization of Computability and Proof of Church's Thesis” (PDF). The Bulletin of Symbolic Logic. 14 (3): 299—350. S2CID 645290. doi:10.2178/bsl/1231081370. CS1 održavanje: Format datuma (veza)
Penrose, Roger (1990) [1989]. The Emperor's New Mind (2ndlocation=New York izd.). Oxford University Press. ISBN 978-0-19-851973-7.

Male Tjuringove mašine

Rogozhin, Yurii (1998). „A Universal Turing Machine with 22 States and 2 Symbols”. Romanian Journal of Information Science and Technology. 1 (3): 259—265. Arhivirano iz originala 2005-03-08. g.
Wolfram, Stephen (2002). Universality in Turing Machines and Other Systems: A New Kind of Science. Wolfram Media. str. 707. ISBN 978-1-57955-008-0.
Brunfiel, Geoff, Student snags maths prize, Nature, October 24. 2007.
Jim Giles (2007), Simplest 'universal computer' wins student $25,000, New Scientist, October 24, 2007.
Alex Smith, Universality of Wolfram’s 2, 3 Turing Machine, Submission for the Wolfram 2, 3 Turing Machine Research Prize.
Vaughan Pratt, 2007, "Simple Turing machines, Universality, Encodings, etc.", FOM email list. October 29, 2007.
Martin Davis, 2007, "Smallest universal machine", and Definition of universal Turing machine FOM email list. October 26–27, 2007.
Alasdair Urquhart, 2007 "Smallest universal machine", FOM email list. October 26, 2007.
Hector Zenil (Wolfram Research), 2007 "smallest universal machine", FOM email list. October 29, 2007.
Todd Rowland, 2007, "Confusion on FOM", Wolfram Science message board, October 30, 2007.
Olivier and Marc RAYNAUD, 2014, A programmable prototype to achieve Turing machines" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).

Ostalo

Davis, Martin (2000). Engines of Logic: Mathematicians and the origin of the Computer. New York: W. W. Norton & Company. ISBN 978-0-393-32229-3.
Robin Gandy, "The Confluence of Ideas in 1936". str. 51–102 in Rolf Herken, see below.
Stephen Hawking, ur. (2005). God Created the Integers: The Mathematical Breakthroughs that Changed History. Running Press. Philadelphia. ISBN 978-0-7624-1922-7.
Herken, Rolf (1995). The Universal Turing Machine—A Half-Century Survey. Springer Verlag. ISBN 978-3-211-82637-9.
Andrew Hodges, (1992). Alan Turing: The Enigma. . Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
Peterson, Ivars (1988). The Mathematical Tourist: Snapshots of Modern Mathematics. New York: W. H. Freeman and Company. ISBN 978-0-7167-2064-5.
Penrose, Roger (1989). The Emporer's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford University Press. Oxford and New York, 1989 (1990 corrections). ISBN 978-0-19-851973-7. .
Strathern, Paul (1997). Turing and the Computer—The Big Idea. Anchor Books/Doubleday. ISBN 978-0-385-49243-0.
Hao Wang, "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63–92 (1957).
Petzold, Charles (16. 6. 2008). The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine. John Wiley & Sons. ISBN 978-0-470-22905-7. CS1 održavanje: Format datuma (veza)
Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. ^{[mrtva veza]}., section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
Kantorovitz, Isaiah Pinchas (2005). „A note on turing machine computability of rule driven systems”. ACM Sigact News. 36 (4): 109—110. S2CID 31117713. doi:10.1145/1107523.1107525.

Spoljašnje veze

Turing Machine on Stanford Encyclopedia of Philosophy
Detailed info on the Church–Turing Hypothesis (Stanford Encyclopedia of Philosophy)
Web Turing Machine Web application to construct and execute Turing machines (Javascript)
Turing Machine-Like Models in Molecular Biology, to understand life mechanisms with a DNA-tape processor.
The Turing machine—Summary about the Turing machine, its functionality and historical facts
The Wolfram 2,3 Turing Machine Research Prize—Stephen Wolfram's $25,000 prize for the proof or disproof of the universality of the potentially smallest universal Turing Machine. The contest has ended, with the proof affirming the machine's universality.
"Turing Machine Causal Networks" by Enrique Zeleny, Wolfram Demonstrations Project.
Turing Machines at DMOZ
Purely mechanical Turing Machine
JSTMSimulator: an open source Turing Machine simulator, written in JavaScript. (source code on GitHub)