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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Універсальна машина Тьюрінга(УМТ) це така машина Тюрінга(МТ) яка може замінити собою будь-яку машину Тьюрінга. Отримавши на вхід програму машини Тьюрінга і вхідні дані, вона вирахує результат, який вирахувала б МТ програма якої була подана на вхід. Концепція даної машини була запропонована Аланом Тьюрінгом у 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]

Використання[ред.ред. код]

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

Посилання[ред.ред. код]

  1. Тюрінг 1936, Девіс 1965:127–128. Приклад згаданого Тюрінгом стандартного опису знаходиться в кінці статті.
  2. Кнут, 1973:225
  3. Баркс, Голдстін, фон Нейман (1946), “Preliminary discussion of the logical design of an electronic computing instrument” 1971.
  4. Кнут, 1973:226
  5. Девіс, 2000:185
  6. Ванг, 1954, 1957:63
  7. Мінський, 1967:200
  8. Рогозін, 1996; Кудлек і Рогозін, 2002
  9. Пенроуз, The Emperor's New Mind: Concerning Computers, Minds and The Laws of Physics, 1989:71-73


Див. також[ред.ред. код]