Універсальна машина Тюрінга(УМТ) це така машина Тюрінга(МТ) яка може замінити собою будь-яку машину Тюрінга. Отримавши на вхід програму машини Тюрінга і вхідні дані, вона вирахує результат, який вирахувала б МТ програма якої була подана на вхід. Концепція даної машини була запропонована Аланом Тюрінгом у 1936. У 1937 році Алан Тюрінг довів, що за допомогою УМТ можна розв'язувати практично необмежену кількість задач.
УМТ на відміну від МТ на стрічці зберігає не лише дані для опрацювання але зберігає і алгоритми обробки даних (програми для МТ). УМТ має свою таблицю переходів згідно котрої вона може зчитувати зі стрічки алгоритм для МТ і виконувати його згідно своїх внутрішніх правил.
Вступ
Кожна МТ обраховує певну фіксовану частково обчислювану функцію від вхідного слова за допомогою свого алфавіту. У цьому сенсі вона працює як комп'ютер з фіксованою програмою. Проте, ми можемо закодувати таблицю команд будь-якої МТ в один рядок символів. Таким чином, ми можемо сконструювати МТ, яка зчитує із стрічки слово, що описує таблицю команд разом з вхідними даними, і обраховує слово так, як це зробила б закодована машина. Тюрінг описав таку конструкцію в деталях у 1936 році:
- «Можливо винайти таку машину, яку можна використовувати для обрахунку будь-якої обчислюваної функції. Якщо на початку інформаційної стрічки цієї машини U записати „стандартний опис“ таблиці команд деякої машини M, тоді U буде обраховувати таку ж саму функцію, як М.»
Комп'ютер з вбудованою програмою
Мартін Девіс висунув аргумент про те, що ідея Тюрінга про записування команд машини в ту ж саму «пам'ять», що і вхідні дані, мала великий вплив на концепцію Джона фон Неймана про перший американський дискретно-символьний (не аналоговий) комп'ютер — EDVAC. Також Девіс зауважив, що автоматична обчислювальна машина (ACE, Automatic Computing Engine) Тюрінга випередила появу мікропрограмування та RISC-процесорів. Кнут називає роботу Тюрінга над ACE-комп'ютерами розробкою «апаратного забезпечення для полегшення зв'язку підпрограм». Так само, як машина Тюрінга надихнула на створення комп'ютерів, так і УМТ сприяла розвитку молодих комп'ютерних наук. Перша серйозна програма фон Неймана для EDVAC «просто раціонально сортувала дані». Кнут помітив, що характерною рисою фон Неймана та Голдстіна є те, що підпрограма стає більше вбудованою в саму програму, ніж у спеціальний реєстр. Далі він зауважив, що:
- «Першу інтерпретовану програму можна буде назвати „універсальною машиною Тюрінга“… Тюрінг також брав участь у цій розробці; інтерпретовані системи для пробного ACE-комп'ютера були написані під його керівництвом.»
Девіс стисло згадує про операційні системи та компілятори як про наслідки з уявлення про програму як про дані. Проте, з цим твердженням можна було посперечатися. В той час (з середини 40-х до середини 50-х) досить мала частина дослідників заглиблювалася в архітектуру нових «цифрових комп'ютерів». (1954), молодий дослідник того часу, зробив наступне спостереження:
- «Тюрінгова теорія про обчислювані функції передувала, проте не дуже вплинула на розвиток сучасної конструкції цифрових комп'ютерів. Ці два аспекти, теорія і практика, розвивались практично незалежно один від одного. Головна причина цього в тому, що логіки зацікавлені у питаннях, які радикально відрізняються від тих, у яких зацікавлені прикладні математики та інженери-електротехніки. Проте, не може не здатися дивним те, що часто одні й ті ж самі ідеї виражаються різними термінами у різних розробках.»
Ванг надіявся на те, що його розробки зможуть «об'єднати два наближення». Дійсно, Мінський підтверджує, що «перше формулювання теорії машини Тюрінга в комп'ютерних моделях з'являється у Ванга». Мінський продовжує це дослідження, демонструючи еквівалентність за Тюрінгом лічильних машин.
Математична теорія
Кодування команд МТ як стрічок зробило можливим в принципі давати відповіді на питання про поведінку інших машин Тюрінга. Для більшості випадків така задача є алгоритмічно нерозв'язною, тобто такі функції не можна обрахувати механічно. Наприклад, проблема визначення того, чи певна МТ зупинить роботу при деяких вхідних даних, також відома як проблема зупинки, в загальному випадку є нерозв'язною за Тюрінгом. Теорема Ріса показує, що будь-яке нетривіальне питання про вивід машини Тюрінга є нерозв'язним. УМТ може обраховувати будь-яку рекурсивну функцію, розв'язувати будь-яку і сприймати будь-яку рекурсивно-перелічувану мову. Згідно тези Черча, клас задач, вирішуваних УМТ, збігається із класом алгоритмічно-розв'язних задач. З цих міркувань УМТ виконує роль стандарту, з яким порівнюються обчислювальні системи. Ті системи, які можуть виконувати роботу УМТ називаються повними за Тюрінгом. Абстрактною версією УМТ є — обчислювана функція, яка може обраховувати значення будь-якої іншої обчислюваної функції. Теорема про УМТ доводить існування такої функції.
Ефективність
Приймемо, що вхідні дані машини Тюрінга подані у алфавіті {0, 1}; будь-який інший алфавіт може бути закодований через {0, 1}. Поведінка машини Тюрінга М визначається її функцією переходу. Ця функція також може бути легко закодована через алфавіт {0, 1}. Розмірність алфавіту машини М, кількість стрічок у ній та кількість станів можна визначити із таблиці значень функції переходу. Потрібні стани та символи можна ідентифікувати за їхньою позицією, тобто зазвичай перші два стани — початковий і кінцевий. Отже, кожну машину Тюрінга можна закодувати через алфавіт {0, 1}. Також приймемо, що будь-яке недопустиме кодування відображає машину в тривіальну МТ, яка відразу зупиняється, і що кожна МТ може мати нескінченну кількість варіантів кодувань, яка досягається додаванням довільної кількості одиниць в кінці (аналог стрічкових коментарів у програмуванні). Ми можемо досягнути такого кодування завдяки існуванню нумерації Ґьоделя та еквівалентності між машинами Тюрінга і μ-рекурсивними функціями. Тож, наша конструкція асоціює кожну бінарну стрічку α з машиною Тюрінга Мα. Виходячи з описаного вище кодування, у 1966 році Хенні та показали, що якщо дана машина Тюрінга Мα при вхідному слові x зупиняється через N кроків, то існує багатострічкова УМТ, яка зупиняється при вхідному слові α, x через CN logN, де C — специфічна для даної машини константа, яка не залежить він вхідного слова x, але залежить від розміру алфавіту М, кількості стрічок у машині та кількості станів.
Найменші машини
Коли Алан Тюрінг висловив ідею універсальної машини, то мав на увазі найпростішу обчислювальну модель, достатньо потужну щоб обрахувати всі можливі функції, які можна обрахувати. Клод Шеннон у 1956 році першим поставив питання про знаходження найменшої можливої УМТ. Він показав, що двох символів вистачає тільки якщо використовується достатня кількість станів (і навпаки), і що завжди можливо «поміняти» символи на стани. Марвін Мінський відкрив у 1962 році УМТ, яка має 7 станів і 4 символи. Інші малі УМТ були пізніше знайдені Юрієм Рогозіним та іншими дослідниками. Якщо позначити за (m, n) клас УМТ з m станами і n символами, знайдені були наступні машини: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) та (2, 18). Машина (4, 6) Рогозіна має лише 22 команди — на даний час це найпростіша відома УМТ. Проте, узагальнення стандартних моделей машин Тюрінга допускає існування ще менших УМТ. Одне з таких узагальнень полягає у тому, щоб дозволити нескінченне повторення слова на одному або обох кінцях вхідного слова, що узагальнює поняття універсальності і відоме як «нестрога» універсальність. Знайдені малі нестрогі УМТ (6, 2), (3,3) і (2,4), які симулюють клітковий автомат за Правилом 110. Також існують інші варіанти стандартної моделі машини Тюрінга, які містять малі УМТ: багатострічкові машини, машини із багатовимірною стрічкою та машини із скінченним автоматом.
Приклад кодування універсальної машини
Тюрінг використовував сім символів {A, C, D, R, L, N, ;} для кодування кожної п'ятірки qlai→qrajdk. Номер кожного стану позначається символом D і повторенням символу A відповідну кількість разів, тобто q3 = «DAAA». Аналогічним чином порожній символ позначається «D», символ «0» — «DC», «1» — «DCC» і так далі. Символи «R», «L» і «N», що позначають рух керуючого прапорця, залишаються без змін. Після кодування кожна команда транслюється у стрічку, як показано у наступній таблиці:
Початковий стан | Символ на стрічці | Запис символу | Напрямок руху | Кінцевий стан | Код початкового стану | Код символу на стрічці | Код записуваного символу | Код напрямку руху | Код кінцевого стану | Трансльований код команди |
---|---|---|---|---|---|---|---|---|---|---|
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 |
Далі коди всіх команд записуються разом, при цьому код починається із символу «;» і вони розділяються символом «;». Отримуємо:
- ;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA
Цей код Тюрінг записав у клітинки, що чергуються — так звані «F-клітинки» — залишаючи «E-клітинки» порожніми. Кінцева трансляція коду на стрічку УМТ полягає у записі двох спеціальних символів («е») один за одним, коду, розділеного порожніми клітинками, і символу «::» в кінці (порожні символи зображені тут крапками для наочності):
- 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», розміщуючи їх у «E-клітинках» справа від символу. Наприклад, позначка поточної інструкції z ставиться справа від символу «;», x розташовується відповідно до поточного стану машини. УМТ буде переставляти ці символи (витираючи і записуючи їх в інших місцях) під час виконання обчислень:
- 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.::……
Таблиця команд для цієї УМТ дуже складна. Ряд інших дослідників (зокрема, Пенроуз) надають приклади інших способів кодування команд для УМТ. Як і Пенроуз, більшість з них використовує лише бінарні символи, тобто символи {0, 1} або {порожній символ, |}. Пенроуз пішов далі і записав код своєї УМТ, що становить майже дві повні сторінки одиниць і нулів.
Використання
- Стек процесора — у стеку і дані і програмний код знаходяться поряд і процесор над ними може робити однакові операції, дана можливість дуже важлива для самомодифікації коду.
- Алгоритми — за допомогою УМТ зручно записувати алгоритми розв'язку задач, які пов'язані із стрічками.
- Перетворення чисел із однієї системи числень в іншу, та їх обчислення.
- Отримання результатів обчислюваних за Тюрінгом функцій.
Див. також
Примітки
- Тюрінг 1936, Девіс 1965:127-128. Приклад згаданого Тюрінгом стандартного опису знаходиться в кінці статті.
- Кнут, 1973:225
- Баркс, Голдстін, фон Нейман (1946), «Preliminary discussion of the logical design of an electronic computing instrument» 1971.
- Кнут, 1973:226
- Девіс, 2000:185
- Ванг, 1954, 1957:63
- Мінський, 1967:200
- Рогозін, 1996; Кудлек і Рогозін, 2002
- Пенроуз, The Emperor's New Mind: Concerning Computers, Minds and The Laws of Physics, 1989:71-73
Джерела
- Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Мир, 1972. — 416 с. . Теория рекурсивных функций и эффективная вычислимость. — М. : (рос.)
- .
- О самоприменимости универсальной машины Тьюринга.
- Универсальная машина Тьюрига.
- Как реализовать самомодифицирующийся код в современных операционных системах.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Universalna mashina Tyuringa UMT ce taka mashina Tyuringa MT yaka mozhe zaminiti soboyu bud yaku mashinu Tyuringa Otrimavshi na vhid programu mashini Tyuringa i vhidni dani vona virahuye rezultat yakij virahuvala b MT programa yakoyi bula podana na vhid Koncepciya danoyi mashini bula zaproponovana Alanom Tyuringom u 1936 U 1937 roci Alan Tyuring doviv sho za dopomogoyu UMT mozhna rozv yazuvati praktichno neobmezhenu kilkist zadach Universalna mashina Tyuringa UMT na vidminu vid MT na strichci zberigaye ne lishe dani dlya opracyuvannya ale zberigaye i algoritmi obrobki danih programi dlya MT UMT maye svoyu tablicyu perehodiv zgidno kotroyi vona mozhe zchituvati zi strichki algoritm dlya MT i vikonuvati jogo zgidno svoyih vnutrishnih pravil VstupKozhna MT obrahovuye pevnu fiksovanu chastkovo obchislyuvanu funkciyu vid vhidnogo slova za dopomogoyu svogo alfavitu U comu sensi vona pracyuye yak komp yuter z fiksovanoyu programoyu Prote mi mozhemo zakoduvati tablicyu komand bud yakoyi MT v odin ryadok simvoliv Takim chinom mi mozhemo skonstruyuvati MT yaka zchituye iz strichki slovo sho opisuye tablicyu komand razom z vhidnimi danimi i obrahovuye slovo tak yak ce zrobila b zakodovana mashina Tyuring opisav taku konstrukciyu v detalyah u 1936 roci Mozhlivo vinajti taku mashinu yaku mozhna vikoristovuvati dlya obrahunku bud yakoyi obchislyuvanoyi funkciyi Yaksho na pochatku informacijnoyi strichki ciyeyi mashini U zapisati standartnij opis tablici komand deyakoyi mashini M todi U bude obrahovuvati taku zh samu funkciyu yak M Komp yuter z vbudovanoyu programoyuMartin Devis visunuv argument pro te sho ideya Tyuringa pro zapisuvannya komand mashini v tu zh samu pam yat sho i vhidni dani mala velikij vpliv na koncepciyu Dzhona fon Nejmana pro pershij amerikanskij diskretno simvolnij ne analogovij komp yuter EDVAC Takozh Devis zauvazhiv sho avtomatichna obchislyuvalna mashina ACE Automatic Computing Engine Tyuringa viperedila poyavu mikroprogramuvannya ta RISC procesoriv Knut nazivaye robotu Tyuringa nad ACE komp yuterami rozrobkoyu aparatnogo zabezpechennya dlya polegshennya zv yazku pidprogram Tak samo yak mashina Tyuringa nadihnula na stvorennya komp yuteriv tak i UMT spriyala rozvitku molodih komp yuternih nauk Persha serjozna programa fon Nejmana dlya EDVAC prosto racionalno sortuvala dani Knut pomitiv sho harakternoyu risoyu fon Nejmana ta Goldstina ye te sho pidprograma staye bilshe vbudovanoyu v samu programu nizh u specialnij reyestr Dali vin zauvazhiv sho Pershu interpretovanu programu mozhna bude nazvati universalnoyu mashinoyu Tyuringa Tyuring takozh brav uchast u cij rozrobci interpretovani sistemi dlya probnogo ACE komp yutera buli napisani pid jogo kerivnictvom Devis stislo zgaduye pro operacijni sistemi ta kompilyatori yak pro naslidki z uyavlennya pro programu yak pro dani Prote z cim tverdzhennyam mozhna bulo posperechatisya V toj chas z seredini 40 h do seredini 50 h dosit mala chastina doslidnikiv zagliblyuvalasya v arhitekturu novih cifrovih komp yuteriv 1954 molodij doslidnik togo chasu zrobiv nastupne sposterezhennya Tyuringova teoriya pro obchislyuvani funkciyi pereduvala prote ne duzhe vplinula na rozvitok suchasnoyi konstrukciyi cifrovih komp yuteriv Ci dva aspekti teoriya i praktika rozvivalis praktichno nezalezhno odin vid odnogo Golovna prichina cogo v tomu sho logiki zacikavleni u pitannyah yaki radikalno vidriznyayutsya vid tih u yakih zacikavleni prikladni matematiki ta inzheneri elektrotehniki Prote ne mozhe ne zdatisya divnim te sho chasto odni j ti zh sami ideyi virazhayutsya riznimi terminami u riznih rozrobkah Vang nadiyavsya na te sho jogo rozrobki zmozhut ob yednati dva nablizhennya Dijsno Minskij pidtverdzhuye sho pershe formulyuvannya teoriyi mashini Tyuringa v komp yuternih modelyah z yavlyayetsya u Vanga Minskij prodovzhuye ce doslidzhennya demonstruyuchi ekvivalentnist za Tyuringom lichilnih mashin Matematichna teoriyaKoduvannya komand MT yak strichok zrobilo mozhlivim v principi davati vidpovidi na pitannya pro povedinku inshih mashin Tyuringa Dlya bilshosti vipadkiv taka zadacha ye algoritmichno nerozv yaznoyu tobto taki funkciyi ne mozhna obrahuvati mehanichno Napriklad problema viznachennya togo chi pevna MT zupinit robotu pri deyakih vhidnih danih takozh vidoma yak problema zupinki v zagalnomu vipadku ye nerozv yaznoyu za Tyuringom Teorema Risa pokazuye sho bud yake netrivialne pitannya pro vivid mashini Tyuringa ye nerozv yaznim UMT mozhe obrahovuvati bud yaku rekursivnu funkciyu rozv yazuvati bud yaku i sprijmati bud yaku rekursivno perelichuvanu movu Zgidno tezi Chercha klas zadach virishuvanih UMT zbigayetsya iz klasom algoritmichno rozv yaznih zadach Z cih mirkuvan UMT vikonuye rol standartu z yakim porivnyuyutsya obchislyuvalni sistemi Ti sistemi yaki mozhut vikonuvati robotu UMT nazivayutsya povnimi za Tyuringom Abstraktnoyu versiyeyu UMT ye obchislyuvana funkciya yaka mozhe obrahovuvati znachennya bud yakoyi inshoyi obchislyuvanoyi funkciyi Teorema pro UMT dovodit isnuvannya takoyi funkciyi EfektivnistPrijmemo sho vhidni dani mashini Tyuringa podani u alfaviti 0 1 bud yakij inshij alfavit mozhe buti zakodovanij cherez 0 1 Povedinka mashini Tyuringa M viznachayetsya yiyi funkciyeyu perehodu Cya funkciya takozh mozhe buti legko zakodovana cherez alfavit 0 1 Rozmirnist alfavitu mashini M kilkist strichok u nij ta kilkist staniv mozhna viznachiti iz tablici znachen funkciyi perehodu Potribni stani ta simvoli mozhna identifikuvati za yihnoyu poziciyeyu tobto zazvichaj pershi dva stani pochatkovij i kincevij Otzhe kozhnu mashinu Tyuringa mozhna zakoduvati cherez alfavit 0 1 Takozh prijmemo sho bud yake nedopustime koduvannya vidobrazhaye mashinu v trivialnu MT yaka vidrazu zupinyayetsya i sho kozhna MT mozhe mati neskinchennu kilkist variantiv koduvan yaka dosyagayetsya dodavannyam dovilnoyi kilkosti odinic v kinci analog strichkovih komentariv u programuvanni Mi mozhemo dosyagnuti takogo koduvannya zavdyaki isnuvannyu numeraciyi Godelya ta ekvivalentnosti mizh mashinami Tyuringa i m rekursivnimi funkciyami Tozh nasha konstrukciya asociyuye kozhnu binarnu strichku a z mashinoyu Tyuringa Ma Vihodyachi z opisanogo vishe koduvannya u 1966 roci Henni ta pokazali sho yaksho dana mashina Tyuringa Ma pri vhidnomu slovi x zupinyayetsya cherez N krokiv to isnuye bagatostrichkova UMT yaka zupinyayetsya pri vhidnomu slovi a x cherez CN logN de C specifichna dlya danoyi mashini konstanta yaka ne zalezhit vin vhidnogo slova x ale zalezhit vid rozmiru alfavitu M kilkosti strichok u mashini ta kilkosti staniv Najmenshi mashiniKoli Alan Tyuring visloviv ideyu universalnoyi mashini to mav na uvazi najprostishu obchislyuvalnu model dostatno potuzhnu shob obrahuvati vsi mozhlivi funkciyi yaki mozhna obrahuvati Klod Shennon u 1956 roci pershim postaviv pitannya pro znahodzhennya najmenshoyi mozhlivoyi UMT Vin pokazav sho dvoh simvoliv vistachaye tilki yaksho vikoristovuyetsya dostatnya kilkist staniv i navpaki i sho zavzhdi mozhlivo pominyati simvoli na stani Marvin Minskij vidkriv u 1962 roci UMT yaka maye 7 staniv i 4 simvoli Inshi mali UMT buli piznishe znajdeni Yuriyem Rogozinim ta inshimi doslidnikami Yaksho poznachiti za m n klas UMT z m stanami i n simvolami znajdeni buli nastupni mashini 15 2 9 3 6 4 5 5 4 6 3 9 ta 2 18 Mashina 4 6 Rogozina maye lishe 22 komandi na danij chas ce najprostisha vidoma UMT Prote uzagalnennya standartnih modelej mashin Tyuringa dopuskaye isnuvannya she menshih UMT Odne z takih uzagalnen polyagaye u tomu shob dozvoliti neskinchenne povtorennya slova na odnomu abo oboh kincyah vhidnogo slova sho uzagalnyuye ponyattya universalnosti i vidome yak nestroga universalnist Znajdeni mali nestrogi UMT 6 2 3 3 i 2 4 yaki simulyuyut klitkovij avtomat za Pravilom 110 Takozh isnuyut inshi varianti standartnoyi modeli mashini Tyuringa yaki mistyat mali UMT bagatostrichkovi mashini mashini iz bagatovimirnoyu strichkoyu ta mashini iz skinchennim avtomatom Priklad koduvannya universalnoyi mashiniTyuring vikoristovuvav sim simvoliv A C D R L N dlya koduvannya kozhnoyi p yatirki qlai qrajdk Nomer kozhnogo stanu poznachayetsya simvolom D i povtorennyam simvolu A vidpovidnu kilkist raziv tobto q3 DAAA Analogichnim chinom porozhnij simvol poznachayetsya D simvol 0 DC 1 DCC i tak dali Simvoli R L i N sho poznachayut ruh keruyuchogo praporcya zalishayutsya bez zmin Pislya koduvannya kozhna komanda translyuyetsya u strichku yak pokazano u nastupnij tablici Pochatkovij stan Simvol na strichci Zapis simvolu Napryamok ruhu Kincevij stan Kod pochatkovogo stanu Kod simvolu na strichci Kod zapisuvanogo simvolu Kod napryamku ruhu Kod kincevogo stanu Translovanij kod komandiq1 porozhnij P0 R q2 DA D DC R DAA DADDCRDAAq2 porozhnij E R q3 DAA D D R DAAA DAADDRDAAAq3 porozhnij P1 R q4 DAAA D DCC R DAAAA DAAADDCCRDAAAAq4 porozhnij E R q1 DAAAA D D R DA DAAAADDRDA Dali kodi vsih komand zapisuyutsya razom pri comu kod pochinayetsya iz simvolu i voni rozdilyayutsya simvolom Otrimuyemo DADDCRDAA DAADDRDAAA DAAADDCCRDAAAA DAAAADDRDA Cej kod Tyuring zapisav u klitinki sho cherguyutsya tak zvani F klitinki zalishayuchi E klitinki porozhnimi Kinceva translyaciya kodu na strichku UMT polyagaye u zapisi dvoh specialnih simvoliv e odin za odnim kodu rozdilenogo porozhnimi klitinkami i simvolu v kinci porozhni simvoli zobrazheni tut krapkami dlya naochnosti 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 Tablicya komand UMT vidpovidaye za rozshifrovku simvoliv Tablicya komand Tyuringa poznachaye yih roztashuvannya markerami u v x y ta z rozmishuyuchi yih u E klitinkah sprava vid simvolu Napriklad poznachka potochnoyi instrukciyi z stavitsya sprava vid simvolu x roztashovuyetsya vidpovidno do potochnogo stanu mashini UMT bude perestavlyati ci simvoli vitirayuchi i zapisuyuchi yih v inshih miscyah pid chas vikonannya obchislen 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 Tablicya komand dlya ciyeyi UMT duzhe skladna Ryad inshih doslidnikiv zokrema Penrouz nadayut prikladi inshih sposobiv koduvannya komand dlya UMT Yak i Penrouz bilshist z nih vikoristovuye lishe binarni simvoli tobto simvoli 0 1 abo porozhnij simvol Penrouz pishov dali i zapisav kod svoyeyi UMT sho stanovit majzhe dvi povni storinki odinic i nuliv VikoristannyaStek procesora u steku i dani i programnij kod znahodyatsya poryad i procesor nad nimi mozhe robiti odnakovi operaciyi dana mozhlivist duzhe vazhliva dlya samomodifikaciyi kodu Algoritmi za dopomogoyu UMT zruchno zapisuvati algoritmi rozv yazku zadach yaki pov yazani iz strichkami Peretvorennya chisel iz odniyeyi sistemi chislen v inshu ta yih obchislennya Otrimannya rezultativ obchislyuvanih za Tyuringom funkcij Div takozhMashina Tyuringa Mashina Posta Skinchennij avtomatPrimitkiTyuring 1936 Devis 1965 127 128 Priklad zgadanogo Tyuringom standartnogo opisu znahoditsya v kinci statti Knut 1973 225 Barks Goldstin fon Nejman 1946 Preliminary discussion of the logical design of an electronic computing instrument 1971 Knut 1973 226 Devis 2000 185 Vang 1954 1957 63 Minskij 1967 200 Rogozin 1996 Kudlek i Rogozin 2002 Penrouz The Emperor s New Mind Concerning Computers Minds and The Laws of Physics 1989 71 73DzherelaHopcroft John E Ullman Jeffrey D 2001 Vstup do teoriyi avtomativ mov i obchislen vid 2nd Addison Wesley s 521 angl inshi movi Teoriya rekursivnyh funkcij i effektivnaya vychislimost M Mir 1972 416 s ros O samoprimenimosti universalnoj mashiny Tyuringa Universalnaya mashina Tyuriga Kak realizovat samomodificiruyushijsya kod v sovremennyh operacionnyh sistemah