Машина Т'юрінга

Матеріал з Вікіпедії — вільної енциклопедії.

Машина Т'юрінга — гіпотетична (абстрактна) машина, яка використовується для визначення поняття алгоритму. Було запропоновано вважати алгоритмом все те, що може бути виконано машиною Т'юрінга, а все, що машина Т'юрінга виконати не здатна вважати не алгоритмом.

[ред.] Історія

Формальні визначення алгоритму з'явилися в тридцятих-сорокових роках 20 сторіччя. Одним із перших було визначення англійського математика А. Т'юрінга, який в 1936 році описав схему деякої гіпотетичної (абстрактної) машини і запропонував називати алгоритмами те, що вміє робити така машина. При цьому визначенні, якщо щось не може бути зроблено машиною Т'юрінга, це вже не алгоритм. Інакше кажучи, Т'юрінг формалізував правила виконання дій за допомогою опису роботи деякої конструкції.

[ред.] Визначення

У кожної машини Т'юрінга є стрічка, потенційно нескінчена в обидві сторони. Є скінчена множина символів стрічки S₀, …, S_n, що називається алфавітом машини. У кожний момент часу кожна комірка може бути зайнята не більш ніж одним символом. Машина має деяку скінчену множину внутрішніх станів q₀, q₁, …, q_n. У кожний даний момент часу машина знаходиться в тільки одному із цих станів.

Нарешті, є голівка, яка у кожний даний момент часу знаходиться на одному із квадратів стрічки. Машина діє не безупинно а лише в дискретні моменти часу. Якщо в якійсь момент t голівка сприймає квадрат (тобто знаходиться на квадраті), що містить символ S_i, і машина знаходиться у внутрішньому стані q_j, то дія машини визначена, і однією із чотирьох дій:

голівка стирає символ S, і записує на тому ж квадраті новий символ S_k,
голівка пересувається в сусідній лівий квадрат,
голівка пересувається в сусідній правий квадрат,
машина зупиняється.

У випадках (1)-(3) машина переходить у новий внутрішній стан q_r, і готова знову до дії в такий момент t + 1. Будемо припускати, що символ S₀ представляє порожній квадрат, і отже, голівка завжди сприймає деякий символ.

Перші три з можливих дій машини можуть бути описані відповідно такими упорядкованими четвірками, які ми надалі будемо називати командами:

$S_i q_j \to S_k q_r S$
$S_i q_j \to S_k q_r L$
$S_i q_j \to S_k q_r R$

Тут перші два символа — це відповідно внутрішні стани машини і сприйнятий символ, наступні три визначають дію машини (запис голівкою символу S_k, або переміщення голівки на один квадрат вліво, або переміщення голівки на один квадрат вправо) та новий стан машини. Якщо стрічка вкладена в машину Т'юрінга, голівка машини встановлена на один із квадратів стрічки і машина приведена в один із своїх внутрішніх станів, то машина починає оперувати на стрічці: її голівка пише і стирає символи і пересувається з одного квадрата в інший. Якщо при цьому машина колись зупиняється, то стрічка, яка знаходиться в ній в цей момент, називається результатом застосування машини до даної стрічки.

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

[ред.] Можливості машини Т'юрінга

Багатство можливостей конструкції Т'юрінга виявляється в тому, що якщо якісь алгоритми A та B реалізуються машинами Т'юрінга, то можна будувати програми машин Т'юрінга, які реалізують композиції алгоритмів A та B, наприклад, виконати A, потім виконати B або виконати A. Якщо в результаті утворилося слово так, то виконати B. У протилежному випадку не виконувати B або виконувати по черзі A, B, поки B не дасть відповідь ні.

У інтуїтивному змісті такі композиції є алгоритмами. Тому їхня реалізація за допомогою машини Т'юрінга служить одним із засобів обґрунтування універсальності конструкції Т'юрінга.

Реалізованість таких композицій доводиться в загальному вигляді, незалежно від особливостей конкретних алгоритмів A та B. Доведення полягає в тому, що вказується засіб побудови з програм A та B програми потрібної композиції. Нехай, наприклад, потрібно побудувати машину A \cdot B, еквівалентну послідовному виконанню алгоритмів A та B. Поки виконується алгоритм A, у програмі A\cdot B працює частина A без урахування частини B. Коли алгоритм A дійде до кінця, то замість останова відбудеться перехід у перший стан частини B, і потім частина B буде працювати звичайним чином, наче частини A і не було.

Аналогічно конструируются й інші композиції машин Т'юрінга; щораз будуються загальні правила: що на що змінювати у вихідних програмах.

Описуючи різноманітні алгоритми для машин Т'юрінга і стверджуючи реалізованість усіляких композицій алгоритмів, Т'юрінг переконливо показав розмаїтість можливостей запропонованої їм конструкції, що дозволило йому виступити з такою тезою:

Всякий алгоритм може бути реалізований відповідною машиною Т'юрінга.

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

Якщо пошук рішення наштовхується на перешкоду, то можна використовувати цю перешкоду для доведення неможливості рішення, спираючись на основну гіпотезу теорії алгоритмів. Якщо ж при доказі неможливості виникає своя перешкода, то вона може допомогти просунутися в пошуку рішення, хоча б частково усунувши стару перешкоду. Так, по черзі намагаючись довести то існування, то відсутність рішення, можна поступово наблизитися до розуміння суті поставленної задачи.

Довести тезу Т'юрінга не можна, тому що в його формулюванні не визначене поняття всякий алгоритм, тобто ліва частина тотожністі. Його можна тільки обґрунтувати, представляючи різноманітні відомі алгоритми у вигляді машин Т'юрінга. Додаткове обґрунтування цієї тези складається в тому, що пізніше було запропоновано ще декілька загальних визначень поняття алгоритму і щораз вдавалося довести, що, хоча нові алгоритмічні схеми і виглядають інакше, вони в дійсності еквівалентні машинам Т'юрінга:

усе, що реалізовано в однієї з цих конструкцій, можна зробити й в інших

Ці твердження доводяться строго, тому що в них мова йде вже про тотожність формальних схем.