Універсальна машина Тюрінга

Кожна МТ обраховує певну фіксовану частково обчислювану функцію від вхідного слова за допомогою свого алфавіту. У цьому сенсі вона працює як комп'ютер з фіксованою програмою. Проте, ми можемо закодувати таблицю команд будь-якої МТ в один рядок символів. Таким чином, ми можемо сконструювати МТ, яка зчитує із стрічки слово, що описує таблицю команд разом з вхідними даними, і обраховує слово так, як це зробила б закодована машина. Тюрінг описав таку конструкцію в деталях у 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, ;} для кодування кожної п'ятірки q_la_i→q_ra_jd_k. Номер кожного стану позначається символом D і повторенням символу A відповідну кількість разів, тобто q3 = «DAAA». Аналогічним чином порожній символ позначається «D», символ «0» — «DC», «1» — «DCC» і так далі. Символи «R», «L» і «N», що позначають рух керуючого прапорця, залишаються без змін. Після кодування кожна команда транслюється у стрічку, як показано у наступній таблиці:

Далі коди всіх команд записуються разом, при цьому код починається із символу «;» і вони розділяються символом «;». Отримуємо:

;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]

• Стек процесора — у стеку і дані і програмний код знаходяться поряд і процесор над ними може робити однакові операції, дана можливість дуже важлива для самомодифікації коду.
• Алгоритми — за допомогою УМТ зручно записувати алгоритми розв'язку задач, які пов'язані із стрічками.
• Перетворення чисел із однієї системи числень в іншу, та їх обчислення.
• Отримання результатів обчислюваних за Тюрінгом функцій.

• «Машина Тюрінга». Вплив математичної теорії зв'язку на логіко-семантичні дослідження.
• О самоприменимости универсальной машины Тьюринга.
• Универсальная машина Тьюрига.
• Как реализовать самомодифицирующийся код в современных операционных системах.

• Машина Тюрінга
• Машина Поста
• Скінченний автомат