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

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

Машини Тюрінга
Машина
Модифікації машини Тюрінга Приклади машини Тюрінга Галерея машин Тюрінга
Варіанти
Змінна машина Тюрінга Нейронна машина Тюрінга Недетермінована машина Тюрінга Квантова машина Тюрінга Машина Поста-Тюрінга Імовірнісна машина Тюрінга Незмінна машина Тюрінга Незмінна машина Тюрінга з рухом праворуч Багатострічкова машина Тюрінга Багатодоріжкова машина Тюрінга Симетрична машина Тюрінга Повна машина Тюрінга Однозначна машина Тюрінга Універсальна машина Тюрінга Машина Зенона
Науковці
Алан Тюрінг Еміль Пост

Універсальна машина Тюрінга(УМТ) це така машина Тюрінга(МТ) яка може замінити собою будь-яку машину Тюрінга. Отримавши на вхід програму машини Тюрінга і вхідні дані, вона вирахує результат, який вирахувала б МТ програма якої була подана на вхід. Концепція цієї машини запропонував Алан Тюрінг у 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, ;} для кодування кожної п'ятірки q_la_i→q_ra_jd_k. Номер кожного стану позначається символом 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} або {порожній символ, |}. Пенроуз пішов далі і записав код своєї УМТ, що становить майже дві повні сторінки одиниць і нулів.

Використання

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

Див. також

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

Джерела

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• «Машина Тюрінга». Вплив математичної теорії зв'язку на логіко-семантичні дослідження.
• О самоприменимости универсальной машины Тьюринга.
• Универсальная машина Тьюрига.
• Как реализовать самомодифицирующийся код в современных операционных системах.