Тјурингова машина

Тјурингова машина је апстрактна "машина" која манипулише симболе на пољу траке према табели правила; тачније, то је математички модел који дефинише такав уређај. Упркос једноставности модела, било који рачунарски алгоритам, Тјурингова машина може бити конструисана тако да је у стању да симулира логику тог алгоритма.

Машина ради на бескрајној траци меморије подељеној у ћелије. Машина позиционира своју главу изнад ћелије и "чита" (скенира) симбол тамо. Затим по симболу и његовом садашњем месту у коначној табели корисничких наведених упутства машина (и) пише симбол (нпр цифре или писмо од коначног алфабета) у ћелији (неки модели омогућавају брисање симбола и / или не писање), затим (ии) или помера једну ћелију траке лево или десно (неки модели омогућавају непокретност, поједини модели померају главу), затим (иии) (како је утврђено у посматраном симболу и месту у табели машине) или наставља с наредним упутством или зауставља рачунање.

Тјурингову машину је изумео 1936. године Алан Тјуринг, коју је назвао А-машина (аутоматска машина). Са овим моделом Тјуринг је био у стању да одговори на два питања у негативном: (1) Да ли постоји машина која може да утврди да ли је било која произвољна машина на свом снимку "кружна" (нпр .замрзне или да не настави свој рачунарски задатак); Слично томе, (2) не постоји машина која може да утврди да ли ће било која произвољна машина на свом снимку икада штампати дати симбол. Тако пружајући математички опис врло једноставног уређаја произвољним израчунавањем, био је у стању да докаже својства рачунања уопште - и посебно, неизрачунљивости Хилбертовог Entscheidungsproblem ("Проблем одлука").

Тако, Тјурингове машине доказују основна ограничења на снази механичког израчунавања. Док они могу изразити произвољне прорачуне, њихов минималистички дизајн их чини неподобним за обрачун у пракси: стварни рачунари су засновани на различитим дизајнима који, за разлику од Тјуринг машине, користе RAM (меморија).

Тјурингова потпуност је способност за систем инструкција да симулирају Тјурингову машину. Програмски језик који је Тјуринг потпун теоретски је у стању да изрази све задатке остварив рачунарима; скоро сви програмски језици су Тјуринг потпуни.

Преглед

Тјурингова машина је општи пример процесора који контролише све манипулације подацима које обавља компјутер. Тачније, то је машина (аутомат) способна да набраја неке произвољне подскупове важећих стрингова алфабета; ови низови су део сета рекурзивног набрајања.

Под претпоставком црне кутије, Тјурингова машина не може знати да ли ће на крају набрајати сваки посебно низ подскупова са датим програмом. То је због чињенице да је халтинг проблем нерешив, који има велике импликације за теоријске границе рачунарства.

Тјурингова машина је у стању да обради граматику без ограничења, што додатно подразумева да је у стању да снажно вреднује логику првог реда бесконачним бројем начина. Ово је славно показано кроз ламбда рачун.

Тјурингова машина која је способна да симулира било коју другу Тјуринг Машину се зове универзална Тјурингова машина (УТМ, или једноставно универзална машина). Много више математички оријентисана дефиниција са сличном "универзалном" природом је увео Алонзо Черч, чији се рад на ламбда рачуну преплиће са Тјуринговим у формалној теорији рачунања која је позната као Чурч-Тјурингова теза. Теза наводи да Тјурингове машине заиста ухвате неформални појам ефикасних метода у логици и математици, и дају прецизну дефиницију алгоритма или "механичког поступка". Студирање својих апстрактних особина даје много увида у информатику и теорије комплексности.

Физички опис

У свом есеју 1948. године, "Интелигентна машина", Тјуринг је написао да је његова машина која се састоји од: ... неограничен капацитет меморије добијене у облику бесконачне траке обележене квадратима, и на сваком симбол може бити одштампан. У сваком тренутку постоји један симбол у машини; то се зове скениран симбол. Машина може мењати скениране симболе, а његово понашање делимично одређује тај симбол, али симболи на траци на другом месту не утичу на понашање машине. Међутим, трака може да се помера напред и назад кроз машину, што је једна од основних операција машине. Било који симбол на траци може, дакле, на крају имати учешће. (Тјуринг (1948). стр. 3)

Неформални опис

Тјурингова машина математички моделира машину која механички ради на траци. На овој траци су симболи који машина може да чита и пише, један по један, користећи главу траке. Операција је у потпуности одређена коначним скупом основних инструкција, као што су "у стању 42, ако је симбол видео 0, напиши 1, а ако је симбол видео 1, промените у стање 17; у стању 17, ако је симбол видео 0, напишите 1 и променити у стање 6; "итд. Оригиналног чланка ("на израчунљивим бројевима, са применом Entscheidungsproblem", види референце испод), Тјуринг није замишљао механизам, али особа кога је назвао "компјутер", који спроводи ова детерминистичка механичка правила ропски (или како Тјуринг каже, "у неповезаном начину").

Овде је унутрашње стање (q1) приказано у глави, и илустрација описује траку као да је бесконачна и напуњена са "0", симбол служи као празно. Системски пуно стање (њена потпуна конфигурација) се састоји од унутрашњег стања, било који не празни симболи на траци (у овој илустрацији "11B"), као и положаја главе у односу над тим симболима, укључујући празнине, односно "011B". (Писање после Минског (1967) п. 121).

Прецизније, Тјурингова машина се састоји од:

Имајте на уму да сваки део машине (тј своје стање, колекције симбола, и употребљене траке у сваком тренутку) и његове акције (као што су штампање, брисање и кретања траке) су коначна, дискретна и различита; то је неограничена количина траке и издржљивост која му даје неограничену количину складишног простора.

Формална дефиниција

Након Хопкрофта и Улмана ( (1979). стр. 148), (једна трака) Тјурингове машине може бити формално дефинисана као седморка M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle

$Q$ је коначан, непразан скуп стања
$\Gamma$ је коначан, непразан скуп трака симбола алфабета
$b\in \Gamma$ је празан симбол (једини симбол дозвољен да се јави на траци бесконачно често на сваком кораку током израчунавања)
$\Sigma \subseteq \Gamma \setminus \{b\}$ је скуп улазних симбола
$\delta :(Q\setminus F)\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ је делимична функција звана функција транзиције, где је L лева промена, R десна промена. (Релативно ретка варијанта омогућава "нема помак", каже N, као трећи елемент другог сета.) Ако \delta није дефинисан на тренутном стању и тренутном симболу траке, онда машина застаје.
$q_{0}\in Q$ је почетно стање
$F\subseteq Q$ је скуп крајњих или прихватања стања. Улазни садржај траке је рекао да буде прихваћен од стране M ако се на крају зауставио на стању из F.

Све што ради по овим спецификацијама је Тјурингова машина.

Седморка за 3-стања заузетог дабра изгледа овако (видети више о заузетости дабра на примерима Тјуринговр машине):

$Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}$
$\Gamma =\{0,1\}$
$b=0$ ("празно")
$\Sigma =\{1\}$
$q_{0}={\mbox{A}}$ (улазно стање)
$F=\{{\mbox{HALT}}\}$
$\delta =$ виђено стање-табела испод

Табела стања за 3 стања, 2 симбола заузетог дабра
Симбол траке	Тренутно стање А			Тренутно стање Б			Тренутно стање C
Симбол траке	Симбол који се пише	Померање траке	Следеће стање	Симбол који се пише	Померање траке	Следеће стање	Симбол који се пише	Померање траке	Следеће стање
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	HALT

Додатни детаљи потребни за визуелизацију или да се спроведу Тјурингове машине

Према речима ван Емде Боаса (1990). стр. 6: "Скуп-теоријски предмет [његов формални опис седморке сличан горе] даје само делимичне информације о томе како ће се машина понашати и како ће његови прорачуни изгледати."

На пример,

Тамо мора бити многих одлука о томе како симболи заправо изгледају, и успешно доказан начин читања и писања симбола унедоглед.
Помак лево и помак десно операције могу померити главу траку преко траке, али заправо када се прави Тјурингова Машина практичније је направити траку слајд напред и назад испод главе умјесто тога.
Трака може бити коначна, и аутоматски продужена са празнинама по потреби (који је најближи математичкој дефиницији), али је чешће да мислимо о томе као бесконачно истезање на оба краја и бити напуњен са празнинама, осим ако је на експлицитно дато коначном одломку глава траке на њему. (Ово је, наравно, неизвршиво у пракси.) Трака не може бити фиксирана у дужини, све док то не би одговарало датој дефиницији и озбиљно ограничити опсег израчунавања машине може обављати са онима који су линеарно ограничен аутомат.

Алтернативне дефиниције

Дефиниције у литератури се понекад мало разликују, праве аргументе или доказе лакшим или јаснијим, али то се увек ради на такав начин да резултујућа машина има исте рачунарске моћи. На пример, промена скупа \{L,R\} у \{L,R,N\}, где би N било ("Ниједан" или "Нема операције") дозвољавају машини да остане на истој ћелији траке уместо да се помера лево или десно, не повећавају рачунарске моћи машине.

Најчешћа конвенција представља сваку "Тјурингову инструкцију" у "Тјурингову табелу" једна од девет петорки, по конвенцији Тјуринг/ Дејвис (Тјуринг (1936) у Неодлучиво. стр. 126-127 и Дејвис (2000) стр . 152):

(дефиниција 1): (q_i, S_j, S_k/E/N, L/R/N, q_m)

( тренутно стање q_i , скениран симбол S_j , одштампај симбол S_k/избриши E/ниједан N , помери_траку_на_квадрат_лево L/десно R/ниједно N , ново стање q_m )

Други аутори (Мински (1967). стр. 119., Хопкрофт и Улман (1979). стр. 158., Стоун (1972). стр. 9.) доносе другачију конвенцију, са новим стањем q_m наведеним одмах након скенираног симбола S_j:

(дефиниција 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

( тренутно стање q_i , скениран симбол S_j , ново стање q_m , одштампај симбол S_k/избриши E/ниједно N , помери_траку_на_квадрат_лево L/десно R/ниједно N )

За остатак овог члана "дефиниције 1" (Тјуринг / Дејвис конвенција) ће се користити.

Пример: табела стања за 3-стања 2-симбола заузетог дабра смањена на петорку
Тренутно стање	Скениран симбол	Одштампај симбол	Помери траку	Завршно (тј. следеће) стање	Петорка
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)

У следећој табели, Тјурингов оригинални модел је дозволио само прве три линије које је назвао N1, N2, N3 ( Тјуринг у Неодлучиво. стр. 126). Он је дозволио брисање "скенираног квадрата" од именовања нулто место симболом S0 = "брисање" или "празно", итд. Међутим, није дозволио за не-штампање, тако да свака линија инструкције укључује "симбол за штампање Sk" или "брисање" (види фусноту 12 у поруци (1947), Неодлучиво pp. 300). Скраћенице су Тјурингове (Неодлучиво pp. 119). Након Тјуринговог оригиналног рада у 1936-1937, модели машина су дозволили свих девет могућих врста петорки:

Тренутна м конфигурација (Тјурингово стање)	Симбол траке	Операција - Штампање	Померање траке	Родитељ м-конфигурације (Тјурингово стање)	Петорка	Коментари петорке	Четворке
N1	q_i	S_j	Штампај(S_k)	Лево L	q_m	(q_i, S_j, S_k, L, q_m)	"Празно" = S₀, 1=S₁, etc.
N2	q_i	S_j	Штампај(S_k)	Десно R	q_m	(q_i, S_j, S_k, R, q_m)	"Празно" = S₀, 1=S₁, etc.
N3	q_i	S_j	Штампај(S_k)	Ниједно N	q_m	(q_i, S_j, S_k, N, q_m)	"Празно" = S₀, 1=S₁, etc.	(q_i, S_j, S_k, q_m)
4	q_i	S_j	Ниједно N	Лево L	q_m	(q_i, S_j, N, L, q_m)	(q_i, S_j, L, q_m)
5	q_i	S_j	Ниједно N	Десно R	q_m	(q_i, S_j, N, R, q_m)	(q_i, S_j, R, q_m)
6	q_i	S_j	Ниједно N	Ниједно N	q_m	(q_i, S_j, N, N, q_m)	Директо "Скочи"	(q_i, S_j, N, q_m)
7	q_i	S_j	Избриши	Лево L	q_m	(q_i, S_j, E, L, q_m)
8	q_i	S_j	Избриши	Десно R	q_m	(q_i, S_j, E, R, q_m)
9	q_i	S_j	Избриши	Ниједно N	q_m	(q_i, S_j, E, N, q_m)	(q_i, S_j, E, q_m)

Било која Тјурингова табела (листа инструкција) се може конструисати од горе наведених девет петорки. Из техничких разлога, три не-штампа или "N" инструкције (4, 5, 6) могу се обично изоставити. За примере погледајте примере Тјурингове машине.

Мање чешћа употреба четворки су наишле: оне представљају још једно распршивање Тјурингових инструкција (Порука (1947), Булос и Џефри (1974, 1999), Дејвис-Сигал-Вијукер (1994)); Види још више у Пост-Тјуринговој машини.

Стање

Реч "стање" коришћена у контексту Тјурингових машина може бити извор забуне, јер то може да значи две ствари. Већина коментатора после Тјуринга су користили "стање" да означе назив / ознаку тренутне инструкције које ће обављати-тј садржај регистра стања. Али Тјуринг (1936) је направио јаку разлику између записа онога што је он назвао машинска"М-конфигурација", (његово унутрашње стање) и машине (или особе) "напредак стања" кроз обрачун - тренутно стање укупног система. Шта је Тјуринг назвао "формула стања" укључује и тренутна упутства и све симболе на траци:

Раније у свом раду Тјуринг је ово носио још даље: он даје пример где је смештен симбол актуелне "М-конфигурације" -ознака инструкције-испод скенираног квадрата, заједно са свим симболима на траци (Неодлучиво. стр. 121); ово он назива "потпуна конфигурација" (Неодлучиво. стр. 118.). За штампање "потпуне конфигурације" на једној линији, он ставља ознаку стања / М-конфигурације са леве стране скенираног симбола.

Варијанта овог се види код Клина (1952), где Стефан Клин показује како написати Гуделов број "ситуација" машина: он ставља "М-конфигурацијски" симбол q4 отприлике у центру преко скенираног квадрата 6 не- празних квадрата на траци (види фигуре Тјурингове-траке у овом чланку) и ставља га десно од скенираног квадрата. Али Клин код себе односи "q4" као "стање машине" (Клин. стр. 374-375). Хопкрофт и Улман зову овај "тренутни опис" сложеним и прате Тјурингову конвенцију стављања "тренутног стања" (ознака упутства, М-конфигурација) са леве стране скенираног симбола ( pp. 149).

Пример: укупно стање 3 стања 2 симбола заузетог дабра након 3 „померања (узето из примера „покрени из фигуре испод):

1A1

То значи: након три потеза трака има ... 000110000.. на њој, глава скенира крајње десно 1, а држава је А. Празнине (у овом случају заступа "0" s) могу бити део од укупног стања као што је приказано овде: В01; трака има једну 1 на њој, али глава скенира 0 ("празан") до њене леве и стање је В.

"Стање" у контексту Тјурингове машине треба да се разјасни како би се што се описује: (и) тренутна инструкција, или (ии) списак симбола на траци заједно са тренутном инструкцијом, или (иии) списак симбола на траци, заједно са тренутним упутством постављеним са леве стране скенираног симбола или са десне стране скенираног симбола.

Тјурингов биограф Ендру Хуџис (1983: 107) је приметио и описао ову конфузију.

Дијаграми стања Тјурингове машине

Табла за 3 стања заузетог дабра (Р = штампај/испиши а „1)
Симбол траке	Тренутно стање A			Тренутно стање B			Тренутно стање C
Испиши симбол	Помери траку	Следеће стање	Испиши симбол	Помери траку	Следеће стање	Испиши симбол	Помери траку	Следеће стање
0	P	R	B	P	L	A	P	L	B
1	P	L	C	P	R	B	P	R	ЗАУСТАВИ

"3-стања заузетог дабра" Тјурингове машине у коначном аутомату. Сваки круг представља "стање" табеле-"М-конфигурација" или "инструкција". "Правац" транзиције стања је приказан стрелицом. Ознака (нпр. 0/P,R) у близини одлазног стања (на "репу" стрелице) специфицира скенирани симбол који изазива одређену транзицију (нпр 0) праћено /, праћен накнадним "понашањем "машине, на пример, "Р Штампа" померите траку "R Десно". Без генералног прихватања формату постоји. Конвенција је показана после МакКлускија (1965), Бута (1967), Хила и Петерсона (1974).

Са десне стране: горњој табели што је изражено као " транзиција стања" дијаграма.

Обично велике табеле је боље оставити као табеле (Бут pp. 74). Оне су лакше симулиране рачунару у облику табеле (Бут. стр. 74). Међутим, одређени појмови-нпр. машине са "Ресетом" стања и машине са обрасцима који се понављају (Хил и Питерсон pp. 244фф) Могу бити лакше виђене када се посматрају као цртеж.

Да ли цртеж представља побољшање у својим табелама мора да одлучи читач за одређени контекст. Погледајте коначни аутомат за више.

Читалац би требало да поново буде упозорен да такви дијаграми представљају снимак њихове табеле замрзнуте у времену, а не курс ("путања") неког рачунања кроз време и / или простора. Док сваки пут заузета дабар машина "ради" увек следи исту путању стања, то није истина за "копију" машине које могу бити пружене са променљивим улазним „параметрима ".

Дијаграм "Напредак у орачунању" показује 3-стања заузетог дабра "стање" (упутство) напредак кроз своје рачунање од почетка до краја. На крајњем десном је Тјурингова "потпуна конфигурација" (Клин "ситуација", Хопкрофт-Улман "тренутни опис") на сваком кораку. Ако је машина требало да буде заустављена и разјашњена празнини како "регистар стања" и цела трака, ове"конфигурације" могу да се користе за поновно рачунање било где у њеном напретку (Тјуринг (1936) Неодлучиво pp. 139–140).

Модели еквивалентни моделу Тјурингове машине

Многе машине које мисле да би могле да имају више рачунарског капацитета него једноставна универзална Тјурингова машина може да се покаже да нема више снаге (Хопкрофт и Улман pp. 159 , Мински (1967)). Оне можда могу да израчунају брже, зависи, или користити мање меморије, или њихов скуп инструкција може бити мањи, али не могу снажније рачунати (тј више математичких функција). (Подсетимо се да је Чурч-Тјурингова теза хипотезира да је ово истина за било коју врсту машине: да све што се може "израчунати" може се израчунати неком Тјуринговом машином.)

Тјурингова машина еквивалентна је потисном аутомату који је направљен флексибилније и концизније опуштајући последњи-у-први-напоље услов њеног стека.

На другом крају, неки врло једноставни модели ће се испоставити да су Тјуринг-еквивалентни, односно да има исту рачунску снагу као модел Тјурингове машине .

Уобичајени еквивалентни модели су Тјурингова машина са више трака, вишеканална Тјурингова машина, машине са улазом и излазом, и недетерминистичка Тјурингова машина (НДТМ) за разлику од детерминистичке Тјурингове машине (ДТМ) за које на табели акција има највише један улаз за сваку комбинацију симбола и државе.

Само чита, Десно покретајуће Тјурингове машине еквивалентне су НДКА (као ДКА конверзијом користећи алгоритам НДКА у ДКА конверзије).

Из практичних и дидактичких намера еквивалент регистар машине може да се користи као уобичајен програмски језик.

Избор ц-машине, пророчке о-машине

Рано у свом раду (1936) Тјуринг чини разлику између "аутоматске машине" -је "покрет ... потпуно зависи од конфигурације" и "избора машине":

...чији је захтев само делимично одређен конфигурацијом ... Када таква машина достигне један од тих двосмислених конфигурација, не може наставити док неки произвољан избор не буде учињен од стране спољног оператера. То би био случај да смо користили машине да се баве аксиоматских системима.
— Неодлучиво . стр. 118

Тјуринг (1936) не разрађује, осим у фусноти у којој он описује како се користи а-машина за "проналазак свих доказивих формула на [Хилберт] рачуну", а не користити машину избора. Он "Претпоставља да су избори увек између две могућности 0 и 1. Сваки доказ ће бити утврђен низом избора i₁, i₂, ..., i_n (i₁ = 0 или 1, i₂ = 0 или 1, ..., i_n = 0 или 1), а самим тим и броја 2ⁿ + i₁2^n-1 + i₂2^n-2 + ... +i_n у потпуности одређује доказ. Аутоматска машина обавља сукцесивно доказ 1, доказ 2, доказ 3, ... "(Фуснота‡, Неодлучиво, стр. 138)

Ово је заиста техника којим детерминистичка (нпр а) Тјурингова машина може да се користи да опонаша дејство једне недетерминистичке Тјурингове машине; Тјуринг је решио ствар у фусноти и чини се да га отпушта из даљег разматрања.

Пророчка машина или о-машина је Тјурингова А-машина која паузира свој прорачун на стању "о" неко време, да заврши своју калкулацију, да "чека одлуку" о "пророку" - неодређеног ентитета "осим рекавши да не може бити машина "(Тјуринг (1939). стр. 166-168 Неодлучиво). Концепт је сада активно у употреби математичара.

Универзалне Тјурингове машине

Имплементација Тјурингове машине

Као што је Тјуринг написао у Неодлучиво, стр. 128 (искошеност додата):

Могуће је да се измисли једна машина која се може користити за рачунање било које израчунљиве секвенце. Ако се ова машина 'У' испоручује са траком на почетку од којих је написан на низ торки одвојене зарезом неке компјутерске машине 'М' , затим ће 'У' израчунати исту секвенцу као 'М'

Овај налаз се сада узима здраво за готово, али у то време (1936) сматрана је запањујућим. Модел рачунања који је Тјуринг назвао својом "универзалном машином" - "У" за кратко сматрана од стране неких (Дејвис (2000)) да су основни теоријски пробој који је довео до појма складиштеног -рачунарског програма.

Тјурингов рад садржи, у суштини, изум модерног рачунара и неке од техника програмирања који га прате.
— Мински (1967). стр. 104

У погледу рачунарске комплексности, универзална Тјурингова машина са више трака мора бити само спорија од логаритамског фактора у односу на машинама које симулира. Овај резултат је добијен 1966. године од стране Хејнија и Р. Е. Стернса. (Арора и Барак, 2009, теорема 1.9)

Поређења са другим стварним машинама

Реализација Тјурингове машине у ЛЕГО-у

Често се каже да су Тјурингове машине, за разлику од једноставнијих аутомата, моћне као праве машине, и да су у стању да изврше било операцију коју прави програм може. Оно што је занемарено у овој изјави је да, због тога што права машина може имати само коначан број конфигурација, ова "прави машина" није ништа друго до линеарно ограничен аутомат. С друге стране, Тјурингове машине су еквивалентне машинама које имају неограничен износ складишног простора за своје прорачуне. Међутим, Тјурингове машине нису намењене за моделирање рачунара, већ су намењене за моделирање самог рачунања. Историјски, компјутери, који рачунају само на њиховој (фиксној) интерној меморији, развијени су тек касније.

Постоје неколико начина да се објасни зашто су Тјурингове машине користан модел реалних рачунара:

Све што прави рачунар може да израчуна, Тјурингова машина може да израчуна. На пример: " Тјурингова машина може да симулира било коју врсту потпрограма нађеног у програмским језицима, укључујући рекурзивне процедуре и неке од познатих параметара-пролазу механизама" (Хопкрофт и Улман pp. 157). Довољно велики КА може моделовати било који стварни рачунар, без обзира на ИО. Дакле, изјава о ограничењима Тјурингових машина ће се примењивати и на стварним рачунарима.
Разлика је само у способности Тјурингове машине да манипулише се неограниченом количином података. Међутим, с обзиром коначним износом времена, Тјурингова машина (као права машина) може манипулисати коначном количином података.
Као Тјурингова машина, права машина може имати свој складишни простор проширен по потреби, куповином више дискова или других медија за складиштење. Ако је снабдевање ових стаза кратко, Тјурингова машина може постати мање корисна као модел. Али, чињеница је да ни Тјурингове машине, ни праве машине не требају астрономске износе складишног простора у циљу обављања корисног рачунања. Потребно време за обраду је обично много већи проблем.
Описи програма праве машине који користе једноставнији апстрактни модели су често много сложенији него описи користећи Тјурингове машине. На пример, Тјурингова машина описује алгоритам може имати неколико стотина стања, док је еквивалентни детерминистички коначни аутомат (ДКА) на датој реалној машини има квадрилион. То чини репрезентацију ДКА неизводљивом да се анализира.
Тјурингове машине описују алгоритме независне од колико меморије користе. Постоји ограничење у меморији у поседу било које тренутне машине, али ово ограничење може произвољно порасти на време. Тјурингове машине омогућавају нам да дајемо изјаве о алгоритама који ће (теоретски) заувек, без обзира на напредак у конвенционалној рачунарској архитектури машине.
Тјурингове машине поједностављују изјаву алгоритама. Алгоритми који раде на Тјуринговим-еквивалентним апстрактним машинама су обично више опште него њихове колеге које раде на стварним машинама, јер они имају произвољно прецизне типове података доступне и никада нећете морати да се баве са неочекиваним условима (укључујући, али не ограничавајући се на, понестајање меморије) .

Један од начина на који су Тјурингове машине сиромашни модели за програме је да се многи стварни програми, као што су оперативни системи и процесор текста, писани да добију неограничен улаз током времена, и стога не зауставе. Тјурингове машине не моделирају такав ток обрачуна (али и даље могу да моделују делове, као што су поједине процедуре).

Експериментални прототип да се постигне Тјурингова машина

Ограничења Тјурингових машина

Рачунарска теорија комплексности

Даље информације: Теорија комплексности

Ограничење Тјурингових машина је да не моделирају предности одређеног аранжмана добро. На пример, модерни компјутери складиштеног-програма су заправо инстанце више специфичног облика апстрактне машине познату као случајни приступ ускладиштеног програма машини или РАСП модела машина. Као Универзална Тјурингова машина на ком РАСП складишти свој "програм" у "Меморији" споља до "упутства" својих коначних стања машине. За разлику од универзалне Тјурингове машине, РАСП има бесконачан број различитих, нумерисаних али неограничених "регистара" меморијских "ћелија" које могу да садрже било који број (види Елгот и Робинсон (1964), Хартманис (1971), а посебно Кук -Речов (1973); референце у РАМ). Распова машина са коначним стањима је опремљена са могућношћу за индиректно адресирање (нпр садржај једног регистра може да се користи као адреса да се наведе још један регистар); тако "програм" РАСП-а може адресовати било који регистар у Регистарској-секвенци. Последица ове разлике је да постоје рачунарске оптимизације које могу да се обављају на основу меморије индекса, које нису могуће у општој Тјуринговој машини; Тако, када се Тјурингове машине користе као основа за скакутаво време које тече, А 'лажна доња граница' може да се докаже на времену које тече одређених алгоритама "(због лажних поједностављује се претпоставка Тјурингове машине). Пример за то је бинарна претрага, алгоритам који може да се покаже да обавља брже када се користи РАСП модел израчунавања него модел Тјурингове машине.

Конкурентност

Друго ограничење Тјурингових машина је да оне не моделују добро конкуренцију. На пример, постоји граница величине целог број који се може израчунати од стране увек-заустављајуће недетерминистичке Тјурингове машине почевши на празној траци. (Видети текст о неограниченом нондетерминизму.) Насупрот томе, постоје увек заустављајући истовремени системи без улаза који могу израчунати цео број од неограничене величине. (Процес може бити креиран са локалним складиштењем који је иницијализован са тачком од 0 који истовремено себи шаље како зауставити и покренути поруку. Када прими Иди поруку, она повећава своје бројање од 1 и шаље себи иди поруку. Када она добија стоп поруку, она престаје са неограниченим бројем у свом локалном складиштењу.)

Историја

Она је описана 1936 од стране Алана Тјуринга

Историјска позадина: рачунске машине

Робин Ганди (1919—1995) студент Алана Тјуринга (1912—1954) и његов доживотни пријатељ-прати порекло појма "рачунарска машина" назад до Бебиџа (око 1834) и заправо предлаже "Бебиџову тезу":

Читав развој и операције су сада способне да се изгубе због машинерије.
— (искошено где је Бебиџ цитиран од стране Гандија. стр. 54)

Гандијева анализа Бебиџове Аналитичке машине описује следећих пет операција (види pp. 52–53.):

Аритметичке функције +, −, × где − указује "правилно" одузимање x − y = 0 ако је y ≥ x
Било који редослед операција је операција
Итерација операције (понавља н пута операција Р)
Условна итерација (понављање н пута на операцији Р условљено "успехом" теста Т)
Условни пренос (тј условни "Иди").

Ганди наводи да "функције које се могу израчунати (1), (2), и (4) су управо оне који су Тјуринг израчунљиве". ( pp. 53). Он наводи и друге предлоге за "Универзијаду рачунских машина", укључујући оне од Перси Луџет (1909), Леонардо Торес Ај Куеведо (1914), Маурис д'Окан (1922), Луис Кофигнал (1933), Ваневар Буш (1936), Хаувард Ајкен (1937). Међутим:

... нагласак је на програмирање фиксног непромењен редоследа аритметичке операције. Основни значај условног понављања и условног трансфера за општу теорију рачунских машина није препознат...
— Ганди pp. 55

Entscheidungsproblem ("проблем одлуке"): Хилбертово десето питање 1900-е

Што се тиче Хилбертових проблема које је поставио чувени математичар Давид Хилберт 1900. године, један аспект проблема # 10 је плутао око 30 година пре него што је управо урамљен. Хилбертов оригинални израз за # 10 гласи:

До 1922. године, овај појам "Entscheidungsproblem" је развио мало, и Х. Бехман је изјавио да

До 1928. године међународног конгреса математичара, Хилберт "је направио његова питања сасвим прецизно. Прво, да ли је математика потпуна ... Друго, да ли је математика у складу ... И треће, да ли је математика одлучива?" (Хуџис pp. 91, Хокинг pp. 1121). Прва два питања су одговорили 1930. Курт Гедел на истом састанку на којем Хилберт је одржао говор за одлазак у пензију (много на жалост Хилберта); треће-Entscheidungsproblem је морао да чека до средине 1930-их.

Entscheidungsproblem је да је одговор прво тражио прецизну дефиницију "дефинитивног општеважећег рецепта", које Принстон професор Алонзо Черч ће доћи да позове "ефективну предвидивост", а 1928. године таква дефиниција није постојала. Али у наредних 6-7 година Емил Пост је развио дефиницију кретања радника од собе до собе писања и брисања ознака по списку упутства (Пост 1936), као и Чурч и његова два ученика Стивен Клин и Ј. Б. Росер употребом Ламбда-рачуна Цркве и Геделове теорије рекурзије (1934). Чурчов рад (објављен 15. април 1936) је показао да је Entscheidungsproblem заиста "неодлучив" и тукли су Тјуринга скоро годину дана (Тјурингов рад поднет 28. маја 1936, објављен јануара 1937). У међувремену, Емил Пост је поднео кратак рад у јесен 1936. године, тако да је Тјуринг барем имао предност над Постом. Док је Чурч судио Тјурингов рад, Тјуринг је имао времена да проучи рад Чурча и дода Додатак где је скицирао доказ који би Чурчов Ламбда-рачун и његова машина израчунала исте функције.

И Пост је само предложио дефиницију предвидивости и критиковао Чурчову "дефиницију", али није доказао ништа.

Тјурингова (аутоматска) машина

У пролеће 1935. године, Тјуринг је као млади мастер студент на Краљевском колеџу Кембриџу, Велика Британија, прихватио изазов ; он је био подстакнут предавањима логичара М. Х. А. Њумана "и научио из њих Геделов рад и Entscheidungsproblem ... Њуман користи реч 'механички' ... У својој читуљи Тјурингу 1955 Њуман пише:

Ганди наводи да:

Док је Ганди веровао да је Њуманова изјава изнад "погрешна", ово мишљење не деле сви. Тјуринг је имао доживотну заинтересованост за машине: "Алан је сањао да измишља писаће машине као дечак; [његова мајка] госпођа Тјуринг је имала писаћу машину и он је добро могао започети питајући се шта је значило звањем писаће машине 'механичком'" (Хуџис pp. 96). Док је на Принстону докторирао, Тјуринг је саградио Булову логику-мултипликатор (види доле). Његова докторска теза, под називом "Системи логике на основу редних бројева ", садржи следећу дефиницију "израчунљиве функције":

EntscheidungsproblemКада се Тјуринг вратио у Велику Британију одмах је постао заједнички одговоран за разбијање немачких тајних кодова створених за шифровање машина под називом "Енигма"; Он је такође постао укључен у дизајну АРМ (Аутоматска Рачунска Машина), "[Тјурингов] АРМ-предлог је био ефикасно самосталан, а њени корени не леже у ЕДВАЦу[америчка иницијатива], али у својој универзалној машини" (Хуџис п. 318). Аргументи и даље настављају у вези са пореклом и природом онога што је именовано од стране Клина (1952) као Тјурингова теза. Али шта је Тјуринг доказао са својим моделом рачунарске-машине се појављује у његовом раду израчунљивих бројева, са захтевом за Entscheidungsproblem (1937):

Тјурингов пример (његов други доказ): Ако је неко питао за опште процедуре да нам каже: "Да ли то машина увек штампа 0", питање је "неодлучивог".

1937–1970: „Дигитални рачунар", рођење "информатике"

Године 1937, док на Принстону ради на докторској дисертацији, Тјуринг је саградио дигитални (Булова логика) мултипликатор од нуле, правећи лично своје електромеханичке релеје (Хуџис. стр. 138). „Аланов задатак је био да отелотворује логичан дизајн Тјурингове машине у мрежи релеја погоном прекидача ..." (Хуџис pp. 138). Док је Тјуринг можда био само у почетку радознао и експериментисао, сасвим искрени-рад у истом правцу иде у Немачку (Конрад Цузе(1938)), и у Сједињене Америчке Државе (Хаувард Аикен) и Џорџ Штибиц (1937); плодови њиховог рада су коришћени од стране Аксиса и савезничке војске у Другом светском рату (Хуџис pp. 298–299). У раним до средине 1950-их Хао Ванг и Марвин Мински смањили су Тјурингову машину у једноставнијем облику (претеча пост-Тјурингове машине Мартин Дејвис); истовремено европски истраживачи су смањили модеран електронски рачунар до рачунара као теоријског објекта еквивалентом ономе што се сада назива "Тјурингова машина". У касним 1950-им и раним 1960-им случајни паралелни развоји Мелзака и Ламбека (1961), Минског (1961), и Шепердсона и Стурџиса (1961) спроводе европске послове даље и смањују Тјурингову Машину до више пријатељске, рачунарски налик апстрактни модел назван Бројач машина; Елгот и Робинсон (1964), Хартманис (1971), Кук и Реков (1973) обављају овај посао даље са регистром машине и модела РАМ-а - али у у основи свега су само Тјурингова машина са више трака са аритметичким- налик скупу- инструкција .

1970–данас: Тјурингова машина као модел за рачунање

Данас, бројач, региструјте се и са случајним приступом машине и њиховом господару Тјурингова машина наставља бити модел избора за теоретичаре који истражују питања у теорији рачунања. Посебно, прорачунска теорија комплексности користи Тјурингова машина:

Канторовиц (2005) Шведска је била прва да покаже најједноставније очигледне заступљености Тјурингових машина објављено академски који обједињује Тјурингове машине са математичким анализама и аналогним рачунарима.

Пример

Тјурингова машина има врло једноставну конструкцију. Састоји се од бесконачне траке, која има на себи кућице у које могу да се уписују симболи, и главе која може да чита и пише симболе. За Тјурингову машину се дефинише азбука симбола која ће се у њој користити, и списак стања у којима глава за читање и писање може да се налази. Дефинишу се почетно стање (С₁), и завршно стање (С_к); почетно стање је стање у коме се машина налази на почетку рада, а када машина дође у завршно стање, престаје са радом. Глава може да се помера за једно поље улево (Л), за једно поље удесно (Д), или да остане у месту (М). У зависности од стања у коме се глава налази, и од симбола који се налази у кућици изнад које је глава постављена, глава ће у ту кућицу уписати одређени симбол, померити се лево или десно (или остати у месту), и променити своје стање. Овај процес се понавља док Тјурингова машина не стигне у завршно стање. Следи пример Тјурингове машине која сабира два броја:

Азбука над којом Тјурингова машина ради је следећа: „1“ (цифра броја), „+“ (знак за сабирање) „α“ (празне кућице)

Машина треба да од низа 1^м+1^н направи низ 1^м+н. На пример, од низа ..αα1111+111αα.. треба да направи низ ..αα1111111αα..

Стања машине су:
- С₁ 1 -> α С₂ Д - ако је глава у стању 1, и налази се над пољем у коме је уписано 1, у то поље се уписује α, глава се помера десно, и прелази у стање 2
- С₂ 1 -> 1 С₂ Д - ако је глава у стању 2, и налази се над пољем у коме је уписано 1, у то поље се уписује 1, глава се помера удесно, и остаје у стању 2
- С₂ + -> 1 С₃ Л - ако је глава у стању 2, и налази се над пољем у коме је уписано +, у то поље се уписује 1, глава се помера улево, и прелази у стање 3
- С₃ 1 -> 1 С₃ Л - ако је глава у стању 3, и налази се над пољем у коме је уписано 1, у то поље се уписује 1, глава се помера улево, и остаје у стању 3
- С₃ α -> α С_к Д - ако је глава у стању 3, и налази се над пољем у коме је уписано α, у то поље се уписује α, глава се помера удесно, и прелази у завршно стање, к

Коментар: Машина полази из стања 1, а глава се налази над пољем где је прва цифра првог сабирка. Она ту прву „1“ брише (уписује „α“), и затим се помера десно све док не наиђе на знак „+“. Уместо знака плус, уписује се „1“, и тиме се два броја спајају у један. Затим се глава помера лево, све док не наиђе на „α“, онда се враћа за једно поље десно (како би била на почетку новог броја), и ту се рад завршава. Ово враћање на почетак није било неопходно.

Види још

Напомене

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. стр. 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

Литература

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

Зоран Огњановић, Ненад Крџавац, Увод у теоријско рачунарство, ФОН, Београд, 2004.

Примарна литература, издања и компилације

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. стр. 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.

Теорија израчунљивости

Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic (3rd изд.). Cambridge UK: Cambridge University Press. ISBN 978-0-521-20402-6.
Boolos, George; Burgess, John; Jeffrey, Richard (2002). Computability and Logic (4th изд.). 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 изд.). 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 изд.). 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. стр. 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. стр. 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. стр. 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.

Черчова теза

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.
Penrose, Roger (1990) [1989]. The Emperor's New Mind (2ndlocation=New York изд.). Oxford University Press. ISBN 978-0-19-851973-7.

Мале Тјурингове машине

Rogozhin, Yurii (1998). „A Universal Turing Machine with 22 States and 2 Symbols”. Romanian Journal of Information Science and Technology. 1 (3): 259—265. Архивирано из оригинала 2005-03-08. г.
Wolfram, Stephen (2002). Universality in Turing Machines and Other Systems: A New Kind of Science. Wolfram Media. стр. 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).

Остало

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". стр. 51–102 in Rolf Herken, see below.
Stephen Hawking, ур. (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.
Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. ^{[мртва веза]}., 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.

Спољашње везе

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)