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

У информатици, универзална Тјурингова машина (УТМ) је Тјурингова машина која може да симулира произвољну Тјурингову машину произвољног улаза. Универзална машина у суштини то постиже читањем како описа машине да ће бити симулирана као и улаз истих из својих трака. Алан Тјуринг је увео ту машину 1936-1937. Овај модел неки сматрају (на пример, Мартин Дејвис (2000)) да су порекло компјутера складиштеног програма искористио Џон фон Нојман (1946), за "Electronic Computing Instrument" која сада носи Фон Нојманово име: Фон Нојманова архитектура. Такође је познат као универзална рачунарска машина, универзална машина (УМ), машина У, У.

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

Увод

Свака Тјурингова машина израчунава одређену фиксну парцијалну израчунљиву функцију од улазних стрингова преко свог писма. У том смислу се понаша као рачунар са фиксним програмом. Међутим, можемо да кодирамо акциони сто било које Тјурингове машине у стринг. Тако можемо конструисати Тјурингову машину да очекује на њеном снимку стринг описује акциони сто праћен описивањем стрингова улазне траке и израчунава траку да би кодирана Тјурингова машина обрачунала. Тјуринг је описао такву конструкцију у потпуности детаљно у својим новинама 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  63).

Ванг се надао да ће његов рад "повезати два приступа." Заиста, Мински то потврђује: "да је прва формулација теорије Тјурингове машине у компјутерима попут модела појављује код Ванга (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). Више о овом примеру види страну Примери Тјурингове Машине.

Тјуринг је користио седам симбола {A, C, D, R, L, N, ;} да кодира сваки 5-торку; како је описано у чланку Тјурингова машина, његове 5-торке су само врста  N1, N2, и N3. Број сваке "m-конфигурације" (упутства, стања) је представљен са "D" праћено унарним низом петице, нпр "q3" = DAAA. На сличан начин кодира симболе празне као "D", симбол "0" као "DC", симбол "1" као DCC, итд. Симболи "R", "L" и "N" остаје као што је.

Након кодирања сваке 5-торке затим "монтира" у стринг као што је приказано у следећој табели:

Тренутна м-конфигурација	Симбол на траци	Штампа- операција	Трака-померање	Коначна м-конфигурација	Тренутна м-конфигурација-код	Симбол траке	Код операције штампања	Код померања траке	Код коначне м-конфигурације	Код 5-торке
q1	празно	P0	R	q2	DA	D	DC	R	DAA	DADDCRDAA
q2	празно	E	R	q3	DAA	D	D	R	DAAA	DAADDRDAAA
q3	празно	P1	R	q4	DAAA	D	DCC	R	DAAAA	DAAADDCCRDAAAA
q4	празно	E	R	q1	DAAAA	D	D	R	DA	DAAAADDRDA

Коначно, кодови за све четири 5-торке су нанизани заједно у коду почето као ";" и одвојено са ";" тј .:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

Овај код је стављен на алтернативним трговима-у "Ф-трговима" - остављајући "Е-ограду" (они су одговорни за брисање) празну. Коначна скупина кода на траци за У-машину се састоји од постављања два специјална симбола ("е") један за другим, затим код издвојили на алтернативним трговима, и на крају два симбола двотачке"::" (празно је приказано овде са "." ради јасноће):

ee.;. D.A.D.D.C.R.D.A.A.;. D.A.A.D.D.R.D.A.A.A.;. D.A.A.A.D.D.C.C.R.D.A.A.A.A.;. D.A.A.A.A.D.D.R.D.A.::......

У-смашински акцијски сто (сто транзиције стања) је одговоран за декодирање симбола. Тјурингов акцијски сто води евиденцију о његовом месту са маркерима ""u", "v", "x", "y", "z" постављајући их у "Е-ограду" на десној страни "означене симболом" - на пример, , да означи инструкцију z се налази на десној страни ";" х држи место у односу на тренутну "m-конфигурацију" DAA. Акцијски сто У-машине ће гурати ове симболе око (брише их и ставља их у различитим локацијама) и рачунање напредује:

ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.AxD.D.R.D.A.A.A.;. D.A.A.A.D.D.C.C.R.D.A.A.A.A.;. D.A.A.A.A.D.D.R.D.A.::......

Тјурингов акцијски сто за његову У-машину је веома умешан.

Известан број других коментатора (нарочито Пенроуз 1989) пружају примере начина да кодирају упутства за Универзалне машине. Како ради Пенросе, већина коментатора користити само бинарни симболе, односно само симболе {0, 1}, или {празно, ознака | }. Пенроуз иде даље и пише да целим својим кодом У-машине (Пенроуз. 71–73). Он тврди да је заиста код У-машине, огроман број који обухвата скоро 2 целе странице 0 и 1. За читаоце заинтересоване за једноставније кодирање за Пост-Тјурингове машине расправа  Дејвиса у Стину (Стин 1980: 251фф) може бити корисно.

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

Види још

• Изменична Тјурингова машина
• Фон Нојманов универзални конструктор - покушај да се направи самореплицирајућа Тјурингова машина
• Тјурингова потпуност
  

Литература

Опште референце

• Arora, Sanjeev; Barak, Boaz . "Complexity Theory: A Modern Approach". Cambridge University Press. 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"

Оригинални радови

• Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF).

Семинални радови

• Hennie, F. C.; Stearns, R. E. (1966). „Two-Tape Simulation of Multitape Turing Machines”. Journal of the ACM. 13 (4): 533—546. S2CID 2347143. doi:10.1145/321356.321362. .

Имплементације

• „Universal Turing Machine”.  Kamvysselis (Kellis), Manolis (1999). "Scheme Implementation of a Universal Turing Machine". self-published.

Формалне потврде

• Asperti, Andrea; Ricciotti, Wilmer (2015). „A formalization of multi-tape Turing machines”. Theoretical Computer Science. 603: 23—42. ISSN 0304-3975. S2CID 17858799. doi:10.1016/j.tcs.2015.07.013. 

Остале референце

• Copeland, Jack, ур. (2004). The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma. Oxford UK: Oxford University Press. ISBN 978-0-19-825079-1. 
• Davis, Martin (1980). „What is Computation”. Ур.: Steen, Lynn Arthur. Mathematics Today: Twelve Informal Essays. New York NY: Vintage Books (Random House). ISBN 978-0-394-74503-9. 
• Goldstine, Herman H.; von Neumann, John. Planning and Coding of the Problems for an Electronic Computing Instrument. Institute for Advanced Study (Rep. 1947 ed.) (Princeton).
• Bell, C. Gordon; Newell, Allen (1971). Computer Structures: Readings and Examples. New York: McGraw-Hill Book Company. стр. 92–119. ISBN 978-0-07-004357-2. 
• Herken, Rolf (1995). The Universal Turing Machine – A Half-Century Survey. Springer Verlag. ISBN 978-3-211-82637-9. 
• Knuth, Donald E.. (1968), The Art of Computer Programming Second Edition, Volume 1/Fundamental Algorithms (First ed.), Addison-Wesley Publishing Company The first of Knuth's series of three texts.
• Kudlek, Manfred; Rogozhin, Yurii (2002). „A universal Turing machine with 3 states and 9 symbols”. Developments in Language Theory. Lecture Notes in Computer Science. 2295. стр. 311—318. ISBN 978-3-540-43453-5. doi:10.1007/3-540-46011-x. CS1 одржавање: Вишеструка имена: списак аутора (веза)
• Minsky, Marvin , "Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory", Proc. Symp. Pure Mathematics. 5. Providence RI: American Mathematical Society. 1962. стр. 229—238. 
• Neary, Turlough; Woods, Damien (2009). „Four Small Universal Turing Machines”. Fundamenta Informaticae. 91 (1). CS1 одржавање: Вишеструка имена: списак аутора (веза)
• Neary, Turlough; Woods, Damien (2009b), Small Weakly Universal Turing Machines, 17th International Symposium on Fundamentals of Computation Theory, Springer LNCS (5699). стр. 262–273
• Penrose, Roger (1989). The Emperor's New Mind. Oxford UK: Oxford University Press. ISBN 978-0-19-851973-7. 
• Rogozhin, Yurii (1996). „Small universal Turing machines”. Theoretical Computer Science. 168 (2): 215—240. doi:10.1016/S0304-3975(96)00077-1. 
• Shannon, Claude . "A Universal Turing Machine with Two Internal States", Automata Studies, Princeton, NJ: Princeton University Press. (1956). стр. 157–165
• Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2. 42  230–65.
• Turing, A. M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”. Proceedings of the London Mathematical Society: 544—546. doi:10.1112/plms/s2-43.6.544. 
• Davis ed, Martin (1965). The Undecidable.  (Reprint ed.). Hewlett, NY: Raven Press. (1938). стр. 115–154. with corrections to Turing's UTM by Emil Post cf footnote 11 pg:299