Універсальна машина Тюрінга
Матеріал з Вікіпедії — вільної енциклопедії.
![](https://upload.wikimedia.org/wikipedia/commons/thumb/2/28/Universal_Turing_machine_%28ua%29.svg/500px-Universal_Turing_machine_%28ua%29.svg.png)
Машини Тюрінга |
---|
Машина |
|
Варіанти |
|
Науковці |
Універсальна машина Тюрінга(УМТ) це така машина Тюрінга(МТ) яка може замінити собою будь-яку машину Тюрінга. Отримавши на вхід програму машини Тюрінга і вхідні дані, вона вирахує результат, який вирахувала б МТ програма якої була подана на вхід. Концепція даної машини була запропонована Аланом Тюрінгом у 1936. У 1937 році Алан Тюрінг довів, що за допомогою УМТ можна розв'язувати практично необмежену кількість задач.
УМТ на відміну від МТ на стрічці зберігає не лише дані для опрацювання але зберігає і алгоритми обробки даних (програми для МТ). УМТ має свою таблицю переходів згідно котрої вона може зчитувати зі стрічки алгоритм для МТ і виконувати його згідно своїх внутрішніх правил.
Кожна МТ обраховує певну фіксовану частково обчислювану функцію від вхідного слова за допомогою свого алфавіту. У цьому сенсі вона працює як комп'ютер з фіксованою програмою. Проте, ми можемо закодувати таблицю команд будь-якої МТ в один рядок символів. Таким чином, ми можемо сконструювати МТ, яка зчитує із стрічки слово, що описує таблицю команд разом з вхідними даними, і обраховує слово так, як це зробила б закодована машина. Тюрінг описав таку конструкцію в деталях у 1936 році:
- «Можливо винайти таку машину, яку можна використовувати для обрахунку будь-якої обчислюваної функції. Якщо на початку інформаційної стрічки цієї машини U записати „стандартний опис“ таблиці команд деякої машини M, тоді U буде обраховувати таку ж саму функцію, як М.»[1]
Мартін Девіс висунув аргумент про те, що ідея Тюрінга про записування команд машини в ту ж саму «пам'ять», що і вхідні дані, мала великий вплив на концепцію Джона фон Неймана про перший американський дискретно-символьний (не аналоговий) комп'ютер — EDVAC. Також Девіс зауважив, що автоматична обчислювальна машина (ACE, Automatic Computing Engine) Тюрінга випередила появу мікропрограмування та RISC-процесорів. Кнут називає роботу Тюрінга над ACE-комп'ютерами розробкою «апаратного забезпечення для полегшення зв'язку підпрограм».[2] Так само, як машина Тюрінга надихнула на створення комп'ютерів, так і УМТ сприяла розвитку молодих комп'ютерних наук. Перша серйозна програма фон Неймана для EDVAC «просто раціонально сортувала дані». Кнут помітив, що характерною рисою фон Неймана та Голдстіна є те, що підпрограма стає більше вбудованою в саму програму, ніж у спеціальний реєстр.[3] Далі він зауважив, що:
- «Першу інтерпретовану програму можна буде назвати „універсальною машиною Тюрінга“… Тюрінг також брав участь у цій розробці; інтерпретовані системи для пробного ACE-комп'ютера були написані під його керівництвом.»[4]
Девіс стисло згадує про операційні системи та компілятори як про наслідки з уявлення про програму як про дані[5]. Проте, з цим твердженням можна було посперечатися. В той час (з середини 40-х до середини 50-х) досить мала частина дослідників заглиблювалася в архітектуру нових «цифрових комп'ютерів». Хао Ванг (1954), молодий дослідник того часу, зробив наступне спостереження:
- «Тюрінгова теорія про обчислювані функції передувала, проте не дуже вплинула на розвиток сучасної конструкції цифрових комп'ютерів. Ці два аспекти, теорія і практика, розвивались практично незалежно один від одного. Головна причина цього в тому, що логіки зацікавлені у питаннях, які радикально відрізняються від тих, у яких зацікавлені прикладні математики та інженери-електротехніки. Проте, не може не здатися дивним те, що часто одні й ті ж самі ідеї виражаються різними термінами у різних розробках.»[6]
Ванг надіявся на те, що його розробки зможуть «об'єднати два наближення». Дійсно, Мінський підтверджує, що «перше формулювання теорії машини Тюрінга в комп'ютерних моделях з'являється у Ванга».[7] Мінський продовжує це дослідження, демонструючи еквівалентність за Тюрінгом лічильних машин.
Кодування команд МТ як стрічок зробило можливим в принципі давати відповіді на питання про поведінку інших машин Тюрінга. Для більшості випадків така задача є алгоритмічно нерозв'язною, тобто такі функції не можна обрахувати механічно. Наприклад, проблема визначення того, чи певна МТ зупинить роботу при деяких вхідних даних, також відома як проблема зупинки, в загальному випадку є нерозв'язною за Тюрінгом. Теорема Ріса показує, що будь-яке нетривіальне питання про вивід машини Тюрінга є нерозв'язним. УМТ може обраховувати будь-яку рекурсивну функцію, розв'язувати будь-яку рекурсивну мову і сприймати будь-яку рекурсивно-перелічувану мову. Згідно тези Черча, клас задач, вирішуваних УМТ, збігається із класом алгоритмічно-розв'язних задач. З цих міркувань УМТ виконує роль стандарту, з яким порівнюються обчислювальні системи. Ті системи, які можуть виконувати роботу УМТ називаються повними за Тюрінгом. Абстрактною версією УМТ є універсальна функція — обчислювана функція, яка може обраховувати значення будь-якої іншої обчислюваної функції. Теорема про УМТ доводить існування такої функції.
Приймемо, що вхідні дані машини Тюрінга подані у алфавіті {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)[8]. Машина (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} або {порожній символ, |}. Пенроуз пішов далі і записав код своєї УМТ, що становить майже дві повні сторінки одиниць і нулів.[9]
- Стек процесора — у стеку і дані і програмний код знаходяться поряд і процесор над ними може робити однакові операції, дана можливість дуже важлива для самомодифікації коду.
- Алгоритми — за допомогою УМТ зручно записувати алгоритми розв'язку задач, які пов'язані із стрічками.
- Перетворення чисел із однієї системи числень в іншу, та їх обчислення.
- Отримання результатів обчислюваних за Тюрінгом функцій.
- ↑ Тюрінг 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.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Роджерс Х.Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с. . (рос.)
- «Машина Тюрінга». Вплив математичної теорії зв'язку на логіко-семантичні дослідження.
- О самоприменимости универсальной машины Тьюринга.
- Универсальная машина Тьюрига.
- Как реализовать самомодифицирующийся код в современных операционных системах.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.