300п|мини|Уметнички приказ Тјурингове машине.

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

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

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

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

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

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

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

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

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

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

Неформални опис Тјурингова машина математички моделира машину која механички ради на траци. На овој траци су симболи који машина може да чита и пише, један по један, користећи главу траке. Операција је у потпуности одређена коначним скупом основних инструкција, као што су "у стању 42, ако је симбол видео 0, напиши 1, а ако је симбол видео 1, промените у стање 17; у стању 17, ако је симбол видео 0, напишите 1 и променити у стање 6; "итд. Оригиналног чланка ("на израчунљивим бројевима, са применом  Entscheidungsproblem", види референце испод), Тјуринг није замишљао механизам, али особа кога је назвао "компјутер", који спроводи ова детерминистичка механичка правила ропски (или како Тјуринг каже, "у неповезаном начину"). десно|мини|300x300п|Овде је унутрашње стање (q1) приказано у глави, и илустрација описује траку као да је бесконачна и напуњена са "0", симбол служи као празно. Системски пуно стање (њена потпуна конфигурација) се састоји од унутрашњег стања, било који не празни симболи на траци (у овој илустрацији "11B"), као и положаја главе у односу над тим симболима, укључујући празнине, односно "011B". (Писање после Минског (1967) п. 121). Прецизније, Тјурингова машина се састоји од:

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

Формална дефиниција Након Хопкрофта и Улмана ( (1979). стр. 148), (једна трака) Тјурингове машине може бити формално дефинисана као седморка M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle је коначан, непразан скуп стања је коначан, непразан скуп трака симбола алфабета је празан симбол (једини симбол дозвољен да се јави на траци бесконачно често на сваком кораку током израчунавања)  је скуп улазних симбола је делимична функција звана функција транзиције, где је L лева промена, R десна промена. (Релативно ретка варијанта омогућава "нема помак", каже N, као трећи елемент другог сета.) Ако \delta није дефинисан на тренутном стању и тренутном симболу траке, онда машина застаје. је почетно стање је скуп крајњих или прихватања стања. Улазни садржај траке је рекао да буде прихваћен од стране M ако се на крају зауставио на стању из F. Све што ради по овим спецификацијама је Тјурингова машина.

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

("празно")

(улазно стање)

виђено стање-табела испод

+ Табела стања за 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): (qi, Sj, Sk/E/N, L/R/N, qm) ( тренутно стање qi , скениран симбол Sj , одштампај симбол Sk/избриши E/ниједан N , помери_траку_на_квадрат_лево L/десно R/ниједно N , ново стање qm ) Други аутори (Мински (1967). стр. 119., Хопкрофт и Улман (1979). стр. 158., Стоун (1972). стр. 9.) доносе другачију конвенцију, са новим стањем qm наведеним одмах након скенираног симбола Sj: (дефиниција 2): (qi, Sj, qm, Sk/E/N, L/R/N) ( тренутно стање qi , скениран симбол Sj , ново стање qm , одштампај симбол Sk/избриши 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 qi Sj Штампај(Sk) Лево L qm (qi, Sj, Sk, L, qm) "Празно" = S0, 1=S1, etc. N2 qi Sj Штампај(Sk) Десно R qm (qi, Sj, Sk, R, qm) "Празно" = S0, 1=S1, etc. N3 qi Sj Штампај(Sk) Ниједно N qm (qi, Sj, Sk, N, qm) "Празно" = S0, 1=S1, etc. (qi, Sj, Sk, qm) 4 qi Sj Ниједно N Лево L qm (qi, Sj, N, L, qm) (qi, Sj, L, qm) 5 qi Sj Ниједно N Десно R qm (qi, Sj, N, R, qm) (qi, Sj, R, qm) 6 qi Sj Ниједно N Ниједно N qm (qi, Sj, N, N, qm) Директо "Скочи" (qi, Sj, N, qm) 7 qi Sj Избриши Лево L qm (qi, Sj, E, L, qm) 8 qi Sj Избриши Десно R qm (qi, Sj, E, R, qm) 9 qi Sj Избриши Ниједно N qm (qi, Sj, E, N, qm) (qi, Sj, E, qm) Било која Тјурингова табела (листа инструкција) се може конструисати од горе наведених девет петорки. Из техничких разлога, три не-штампа или "N" инструкције (4, 5, 6) могу се обично изоставити. За примере погледајте примере Тјурингове машине.

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

Стање