У информатици, универзална Тјурингова машина (УТМ) је Тјурингова машина која може да симулира произвољну Тјурингову машину произвољног улаза. Универзална машина у суштини то постиже читањем како описа машине да ће бити симулирана као и улаз истих из својих трака. Алан Тјуринг је увео ту машину 1936-1937. Овај модел неки сматрају (на пример, Мартин Дејвис (2000)) да су порекло компјутера складиштеног програма искористио Џон фон Нојман (1946), за "Electronic Computing Instrument" која сада носи Фон Нојманово име: Фон Нојманова архитектура. Такође је познат као универзална рачунарска машина, универзална машина (УМ), машина У, У.
У погледу рачунарске комплексности, универзална Тјурингова машина са много трака мора бити само спорија од логаритамског фактора у односу на машине које симулира.
Увод десно|500x500px Свака Тјурингова машина израчунава одређену фиксну парцијалну израчунљиву функцију од улазних стрингова преко свог писма. У том смислу се понаша као рачунар са фиксним програмом. Међутим, можемо да кодирамо акциони сто било које Тјурингове машине у стринг. Тако можемо конструисати Тјурингову машину да очекује на њеном снимку стринг описује акциони сто праћен описивањем стрингова улазне траке и израчунава траку да би кодирана Тјурингова машина обрачунала. Тјуринг је описао такву конструкцију у потпуности детаљно у својим новинама 1936.: "Могуће је измислити једну машину која може да се користи за рачунање било којих израчунљивих стрингова. Ако је ова машина У испоручује са траком на почетку која је написана С. Д [" Стандардни опис "акционог стола] неке рачунарске машине М, тада У може израчунати исту секвенцу као М. "
Складиштени програмски рачунар Дејвис даје убедљив аргумент да је Тјурингова концепција о томе шта је сада познато као "складиштени програмски рачунар", од постављања "акционог стола" -инструкције за машину, у истој "меморији" као и улазни подаци, снажно утицала Џон фон Нојманова концепција првог америчког дискретног-симбола (за разлику од аналогног) рачунара-и EDVAC. Дејвис цитира магазин Тајм у том смислу, да "свако ко куца на тастатури ... ради на инкарнацији Тјурингове машине" и да је "Џон фон Нојман [направио] на раду Алана Тјуринг" (Дејвис, 2000: 193 цитирајући магазин Тајм од 29. марта 1999).
Дејвис прави случај да је Тјурингов аутоматски рачунски систем (АРС) рачунар "очекивао" појмове микропрограмирања (Микропрограм) и RISC процесорима (Дејвис 2000: 188). Кнут наводи Тјурингов рад на ACE рачунару као дизајнирање "хардвера да би се олакшала потпрограм повезивања" (Кнут 1973: 225); Дејвис је такође референцирао овај посао као Тјурингово коришћење хардверског "стека" (Дејвис, 2000: 237 фуснота 18).
Како је Тјурингова машина подстицала изградњу рачунара, УТМ је подстицала развој у повоју информатике. Рани, ако не и први, монтер је предложен "од младог пакленог програмера" за ЕДВАЦ (Дејвис 2000: 192). Фон Нојманов "Први озбиљан програм ... [био је] да је једноставно сортирање података ефикасно" (Дејвис 2000: 184). Кнут примећује да се потпрограм који се враћа уграђен у самом програму, а не у посебним регистрима се приписује фон Нојману и Голдштајнеру. Кнут даље наводи да "Прва рутина тумачења може се рећи да је" Универзална Тјурингова машина "... Рутине тумачења у конвенционалном смислу је поменуо Џон Мочли у својим предавањима у школи Мур 1946... Тјуринг је учествовао у том развоју такође; системи тумачења за Пилот АЦЕ рачунара су написани под његовом управом "(Кнут 1973: 226).
Дејвис кратко помиње оперативне системе и преводиоце, као резултата појма програмских-као-подаци (Дејвис 2000: 185).
Неки, међутим, могу подићи питања са овим проценама. У то време (средином 1940-их до средине 1950-их) релативно мали кадар истраживача је блиско повезан са архитектуром нових "дигиталних рачунара". Хао Ванг (1954), млади истраживач у овом тренутку, је изразио следеће запажање: Тјурингова теорија израчунљивих функција је застарео, али није много утицао на велику стварну изградњу дигиталних рачунара. Ова два аспекта теорије и праксе развијене су скоро у потпуности независно један од другог. Главни разлог је несумњиво да се логичари који су заинтересовани за питања радикално разликују од оних чиме се примењени математичари и електо инжењери првенствено баве. Не могу, међутим, неуспешно да погоде један као прилично чудан да су често исти концепти изразили веома различите услове у два развоја "(Ванг. ).
Ванг се надао да ће његов рад "повезати два приступа." Заиста, Мински то потврђује: "да је прва формулација теорије Тјурингове машине у компјутерима попут модела појављује код Ванга (1957)" (Мински 1967: 200). Мински наставља да показује Тјурингову еквивалентност кантер машине.
Што се тиче смањења рачунара на једноставне Тјурингове еквивалентне моделе (и обрнуто), Минскијева ознака Ванга као што је "прва формулација" је отворена за расправу. Иако обе књиге. Минскијева из 1961. године и Вангова из 1957. цитирају Шепердсона и Стурџиса (1963), оне такође наводе и сумирају у неким детаљима рад европских математичара Капенст (1959), Ерсов (1959), и Питер (1958). Имена математичара Хермес (1954, 1955, 1961) и Капенст (1959) појављују се у библиографији оба, и Шепердсон-Стурџиса (1963) и Елгот-Робинсона (1961). Два друга значајна имена су канадски истраживачи Мелзак (1961) и Ламбек (1961). За много више погледајте Еквиваленције Тјурингове машине; референце се могу наћи на Региструјућој машини.
Математичка теорија Са овим кодирањем акционих табела и низова постаје могуће, у принципу, за Тјуринг машине да одговори на питања о понашању других Тјуринг машина. Већина ових питања, међутим, су нерешива, што значи да је у питању функција која се не може механички израчунати. На пример, проблем утврђивања да ли ће произвољна Тјурингова машина зауставити на одређеном улазу, или на свим улазима, познато као Халтинг проблем, је показао да, генерално, нерешиво у Тјуринговом оригиналном раду. Рајсова теорема показује да било које не-тривијално питање о излазу на Тјуринговој машини је нерешив.
Универзална Тјурингова машина може да израчуна било коју рекурзивну функцију, одлучује о било којем рекурзивном језику, и прихватити сваки рекурзивно пребројив језик. Према Чурч-Тјуринговој тези, проблеми решиви Универзалном Тјуринговом машином су управо ти проблеми решиви алгоритмима или ефикасном методом обрачуна, за било какве разумне дефиниције тих појмова. Из тих разлога, Универзална Тјурингова машина служи као стандард према коме се упоређују рачунарски системи, као и систем који може да симулира Универзалну Тјурингову Машину и она се зове Тјуринг потпуна.
Апстрактна верзија Универзалне Тјурингове машине је универзална теорема, рачунарска функција која се може користити за израчунавање неке друге рачунарске функције. Универзална теорема доказује постојање такве функције.
Ефикасност Без губитка општости, улаз Тјурингове машине може се претпоставити да је у алфабету {0, 1}; било који други коначни алфабет може бити кодиран преко {0, 1}. Понашање Тјурингове машине М утврђено је његовом транзицијском функцијом. Ова функција се такође може лако кодирати као стринг над алфабетом {0, 1}, . Величина алфабета М, број трака које има, и величина простора стања се може закључити из стола транзицијске функције. Истакнуте државе и симболи могу бити идентификовани по свом положају, на пример прве два стања могу да по обичају буду крени и заустави стање. Према томе, свака Тјурингова машина може да се кодира као стринг над алфабетом {0, 1}. Осим тога, ми сазивамо да свако неважеће кодирање мапе на тривијалној Тјуринговој машини одмах престане, и да свака Тјурингова машина може имати неограничен број кодирања постављањем кодирања са произвољним бројем (рецимо) 1 на крају, баш као и коментаре раде у програмском језику. То не би требало да буде никакво изненађење да можемо постићи то кодирање с обзиром на постојање Гуделовог броја и рачунарске еквиваленције између Тјурингове машине и μ-рекурзивне функције. Слично томе, наша конструкција асоцира на сваки бинарни стринг α, Тјурингове машине Mα.
Полазећи од наведеног кодирања, 1966 Ф. К. Хејни и Р. Е. Стернс показалу су да дата Тјурингова машина Мα која се зауставља на улазу х у Н корака, онда постоји мулти-трака универзалне Тјурингове машине која зауставља на улазу α, x (с обзиром на различите траке) у CN log N, где је C специфичн константа машине која не зависи од дужине улаза x, али не зависе од М азбучне величине, броја трака, и броја стања. Ефективно, ово је О (N log N) симулација.
Најмање машине Када је Алан Тјуринг дошао на идеју универзалне машине имао је у виду најједноставнији модел рачунара довољно снажан да се израчунају све могуће функције које се могу израчунати. Клод Шенон је прво експлицитно поставио питање проналажења најмање могуће универзалне Тјурингове машина у 1956. Он је показао да су два симбола била довољна све док се користи стање (или обрнуто), и да је увек било могуће разменити стања симбола.
Марвин Мински је открио 7-стањску 4-симболску универзалну Тјурингову Машину 1962. користећи 2-означавајућа система. Друге мале универзалне Тјурингове машине су у међувремену пронађене од стране Јурија Рогожина и други су проширивали овај приступ симулације ознака система. Уколико означимо од (m, n) класа УТМС словом m стања и n симболе следећу торку су пронашли: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), и (2, 18). Рогожинова (4, 6) машина користи само 22 инструкције, и нестандардна УТМ мање описне сложености је позната.
Међутим, генерализујући стандардни модел Тјурингове машине он признаје чак и мање УТМ-е. Једна таква генерализација је да омогући континуално понављане речи о једној или обе стране улаза Тјурингове машине, чиме продужава дефиницију универзалности и познато као "полу-слаба" или "слаба" универзалност. Полу-слабе универзалне Тјрингове машине које симулирају Правило 110 ћелијског аутомата су дате за (6, 2), (3, 3) и (2, 4) стање-симбол парова. Доказ о универзалности за Волфрамову 2-стања3-симбола Тјурингову машину додатно проширује појам слабе универзалности, дозвољавајући одређене непериодичне почетне конфигурације. Друге варијанте на стандардним моделом Тјурингове машине које дају мале УТМ-е укључују машине са више трака или трака вишеструких димензија, и машина заједно са коначним аутоматом.
Машине без унутрашњих стања Ако дозволите више глава на Тјуринговој машини онда можете имати Тјуринг Машине без икаквих унутрашњих стања уопште. "Стања" су кодирана као део траке. На пример, размотримо траку са 6 боја: 0, 1, 2, 0А, 1А, 2А. Размислите о траци као што је 0,0,1,2,2А, 0,2,1 где се троглава Тјурингова машина налази преко троструког (2,2А, 0). Правила онда претварају било коју троструку у другу троструку и помера 3-главе улево или удесно. На пример, правила могу претворити (2,2А, 0) до (2,1,0) и померати главу лево. Тако се у овом примеру машина понаша као тробојна Тјурингова машина са унутрашњим стањима А и Б (заступа без слова). Случај за двоглаву Тјурингову машину је врло слична. Тако двоглава Тјурингова машина може бити универзална са 6 боја. Није познато који је најмањи број боја потребан за вишеглаву Тјурингову машину или ако је двобојна Универзална Тјурингова машина могућа са више глава. То такође значи да се преправе правила Тјуурингове потпуности јер су трострука правила еквивалентна да преправе правила. Проширивањем траке на две димензије са главом узорковања слова и то су 8 комшија, само 2 боје су потребне, као на пример, боја може да се кодира у вертикалном троструком обрасцу као што је 110.
Пример кодирања универзалне машине За оне који би предузели изазов дизајнирања УТМ тачно онако како је навео Тјуринг - видели чланак Дејвис у Коупленду (2004: 103фф). Дејвис исправља грешке у оригиналу и показује како би низ узорака изгледао. Он тврди да је успешно покренута (донекле поједностављен) симулација.
Следећи пример је узет од Тјуринга (1936). Више о овом примеру види страну Примери Тјурингове Машине.