| Стан | Читання | Запис | Рух | Новий стан |
|---|
Алан Тюрінг запропонував свою абстрактну обчислювальну машину у знаковій статті 1936 року «Про обчислювані числа», щоб довести нерозв'язність задачі зупинки. Машина Тюрінга складається з нескінченної стрічки комірок (кожна містить символ із скінченного алфавіту), головки зчитування-запису, що рухається по одній клітинці, і скінченної таблиці переходів: за поточним станом і символом під головкою таблиця вказує новий символ для запису, напрям руху (вліво або вправо) та наступний стан. За тезою Черча-Тюрінга, будь-яка фізично реалізована обчислювальна машина не перевершує машину Тюрінга за класом обчислюваних функцій.
Симулятор надає анімовану покрокову стрічку з виділеною головкою, повну таблицю переходів і п'ять вбудованих програм: двійкове інкрементування, унарне додавання, перевірка паліндрому, копіювання рядка та «зайнятий бобер». Можна зупинитися на будь-якому кроці, переглянути стрічку та змінити таблицю переходів.
Що таке задача зупинки і чому жодна машина Тюрінга не може її розв'язати?
Задача зупинки запитує: чи зупиниться дана машина Тюрінга M на заданому вхідному слові w? Тюрінг у 1936 р. довів, що жоден загальний алгоритм не може відповісти на це для всіх пар (M, w). Доказ є діагональним аргументом: якщо припустити існування детектора зупинки H, можна побудувати машину D, яка протилежна тому, що H передбачає для неї самої — суперечність.
Що таке задача «зайнятого бобра»?
Функція BB(n) — максимальна кількість одиниць, яку може записати n-стан, 2-символьна машина Тюрінга на порожній стрічці перед зупинкою. Відомі значення: BB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13, BB(5)≥4098, BB(6)≥10^10^10^10^10^7. BB(n) зростає швидше за будь-яку обчислювану функцію, що доводить її необчислюваність.
Чи є сучасні комп'ютери просто машинами Тюрінга?
З погляду обчислюваності — так, за тезою Черча-Тюрінга. Будь-яку функцію, яку може обчислити ваш комп'ютер, може обчислити і достатньо велика машина Тюрінга. Однак ефективність різко відрізняється: операції за поліноміальний час на RAM-моделі можуть потребувати експоненціальних кроків головки на однострічковій машині.
Функція переходів δ відображає (поточний_стан, прочитаний_символ) → (новий_символ, напрям, наступний_стан). Для 3-стан, 2-символьної машини таблиця має 6 записів. Кожен запис — п'ятірка: (q, s) → (s', D, q'), де D ∈ {L, R}. Стани зупинки (прийом/відхилення) не мають вихідних переходів — машина зупиняється, потрапивши в один із них.
Універсальна МТ приймає на вхід закодований опис будь-якої іншої МТ M разом із вхідними даними M і покроково симулює обчислення M. Це теоретична основа універсальних комп'ютерів. Мінський (1962) показав, що УМТ можна побудувати всього з 7 станами та 4 символами; менші варіанти з 2 станами та 18 символами також доведено універсальними.
Програма читає стрічку справа (молодший біт) наліво, перетворюючи кожну 1 на 0 (перенос), доки не знайде 0 (або порожню клітинку) — тоді записує 1 і зупиняється. Для вхідних даних «1011» (11₁₀) машина записує «1100» (12₁₀). Максимальна кількість кроків — O(n), де n — кількість бітів.
Мова є розв'язною, якщо МТ завжди зупиняється і правильно приймає або відхиляє кожен рядок. Вона є розпізнаваною (рекурсивно перелічуваною), якщо МТ приймає кожен рядок у мові, але може зациклитися на рядках поза нею. Задача зупинки розпізнавана, але не розв'язна.
Двостанова, тристрічкова машина Тюрінга доведена Тьюрінг-повною Алексом Смітом у 2007 р. (він виграв приз $25 000 від Вольфрама). Чи є двостанова, двосимвольна машина Тьюрінг-повною — відкрите питання. УМТ Сміта (2 стани, 3 символи) — найменша відома.
k-стрічкова МТ має k незалежних стрічок і головок, що рухаються одночасно. Такі машини обчислювально еквівалентні одностріч ковим, але є квадратичне сповільнення при симуляції: O(T(n)) кроків k-стрічкової машини симулюються за O(T(n)²) кроків на одній стрічці. У теорії складності багатострічкові машини є стандартною моделлю для визначення класів P і NP.
Недетермінована МТ (НМТ) може мати кілька дійсних переходів для однієї пари (стан, символ) і «приймає», якщо хоча б одна гілка її дерева обчислення досягає стану прийняття. Клас NP — це саме клас задач, розв'язних поліноміальною за часом НМТ. Питання P = NP залишається найвідомішою невирішеною проблемою математики.
Теорема стиснення стрічки стверджує, що будь-яка МТ, що використовує простір S(n), може бути симульована МТ, що використовує S(n)/c простору для будь-якої константи c, ціною певного часового накладання. Аналогічно, будь-яка МТ з алфавітом розміру k може бути симульована двійковою МТ із константним часовим коефіцієнтом. Такі результати дозволяють теоретикам працювати з двійковими алфавітами без втрати загальності.