Перегляд вихідного коду сторінки Машина Тюрінга

{{Тюрінг}}
{{Теорія автоматів}}
'''Маши́на Тю́рінга'''&nbsp;— математичне поняття, введене для формального уточнення інтуїтивного поняття '''[[алгоритм]]у'''. Названа на честь англійського математика [[Алан Тюрінг|Алана Тюрінга]], який запропонував це поняття у [[1936]]. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик [[Еміль Пост]].<ref name="ekib">[[Енциклопедія кібернетики]], т. '''2''', с. 444—446.</ref>

Основна ідея, що лежить в основі машини Тюрінга, дуже проста. Машина Тюрінга&nbsp;— це [[Абстрактний автомат|абстрактна машина]] (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ у комірку або пересунути голівку на одну комірку ліворуч або праворуч.<ref name="gmbm">Good Math, Bad Math, [http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php Basics: The Turing Machine (with an interpreter!)] {{Webarchive|url=https://web.archive.org/web/20120211065906/http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php |date=2012-02-11 }}, 9 лютого 2007.</ref>

== Історія ==

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

== Визначення ==
У кожної машини Тюрінга є '''стрічка''', потенційно [[Нескінченність|нескінченна]] в обидві сторони. Є [[скінченна множина]] символів стрічки ''S<sub>0</sub>'', …, ''S<sub>n</sub>'', що називається ''алфавітом машини''. У кожен момент часу кожна комірка може бути зайнята не більш ніж одним символом. Машина має деяку [[скінченна множина|скінченну множину]] ''внутрішніх станів'' ''q<sub>0</sub>'', ''q<sub>1</sub>'', …, ''q<sub>n</sub>''. У кожен даний момент часу машина знаходиться лише в одному із цих станів.

Нарешті, є '''голівка''', яка у кожен даний момент часу знаходиться на одній із комірок стрічки. Машина діє не безупинно, а лише у дискретні моменти часу. Якщо у якийсь момент ''t'' голівка сприймає комірку (тобто знаходиться на комірці), що містить символ ''S<sub>i</sub>'', і машина знаходиться у внутрішньому стані ''q<sub>j</sub>'', то дія машини визначена однією із чотирьох дій:
:# голівка затирає символ ''S<sub>i</sub>'', і записує у тій же комірці новий символ ''S<sub>k</sub>'', 
:# голівка пересувається в сусідню ліву комірку, 
:# голівка пересувається в сусідню праву комірку, 
:# машина зупиняється. 

У випадках (1)-(3) машина переходить у новий внутрішній стан ''q<sub>r</sub>'', і готова знову до дії у наступний момент ''t + 1''. Припустимо, що символ ''S<sub>0</sub>'' представляє порожню комірку, і отже, голівка завжди сприймає деякий символ.

Перші три з можливих дій машини можуть бути описані відповідно такими упорядкованими четвірками, які називаються ''командами'': 
:# <math>S_i q_j \to S_k q_r S</math>
:# <math>S_i q_j \to S_k q_r L</math>
:# <math>S_i q_j \to S_k q_r R</math>

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

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

== Можливості машини Тюрінга ==
[[Файл:TuringBeispielDiskretAnimatedGIF_uk.gif|thumb|250px|Схематична ілюстрація роботи машини Тюрінга.]]
Багатство можливостей конструкції Тюрінга виявляється в тому, що 
якщо якісь алгоритми ''A'' та ''B'' реалізуються машинами Тюрінга, то можна будувати програми машин Тюрінга, які реалізують [[Композиція|композиції]] алгоритмів ''A'' та ''B'', наприклад, виконати ''A'', потім виконати ''B'' або виконати ''A''. Якщо в результаті утворилося слово ''так'', то виконати ''B''. У протилежному випадку не виконувати ''B'' або виконувати по черзі ''A'', ''B'', поки ''B'' не дасть відповідь ''ні''. 

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

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

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

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

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

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

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

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

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

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

== Машини еквівалентні звичайній МТ ==
=== Недетермінована МТ ===
Може перебувати в кількох конфігураціях одночасно. Еквівалентна звичайній МТ.

=== Стрічка обмежена зліва ===
Читаюча голівка не може переміщуватись лівіше початкового символу. Еквівалентна звичайній МТ.

=== k-доріжкова машина ===
Голівка може змінювати символ на певній доріжці окремо. Моделюється звичайною МТ, якщо брати алфавіт звичайної як k-ту степінь алфавіту k-доріжкової.

=== k-стрічкова машина ===
На відміну від k-доріжкової, тут кожна стрічка має свою головку, які можуть рухатись окремо. Моделюється 2<sup>k</sup> стрічковою машиною, тому теж еквівалентна звичайній МТ.

=== k-голівкова машина ===
Машина яка має k-голівок, і одну стрічку.

=== Машина з k-вимірною стрічкою ===


== Обмежені машини Тюрінга ==
=== Машина без запису на вхідну стрічку (off-line) ===
Такі машини поділяються на односторонні (голівка може рухатись в обидві сторони), та двосторонні (тільки в одну). Наприклад [[скінченний автомат]] є односторонньою off-line МТ.

=== Лінійно обмежений автомат (ЛОА) ===
МТ з стрічкою що обмежена розмірами вхідного слова

=== Магазинний автомат (МА) ===

Такий автомат має обмежений набір операцій зі стрічкою, а саме:
# Дописати символ <math>\neq \lambda</math> в кінці робочої зони, і пересунутись вправо.
# Пересунутись вліво, і витерти символ під голівкою (замінити на <math>\lambda</math>).

За допомогою {{iw|автомат з двома магазинами|автомата з двома магазинами|de|Zweikellerautomat}} ({{lang-en|TPDA, 2-PDA}}) можна промоделювати роботу [[машина Тьюрінга|машини Тьюрінга]].<ref>{{cite web |title=Is a push-down automaton with two stacks equivalent to a turing machine? |url=https://cs.stackexchange.com/a/2833 |website=Computer Science Stack Exchange |accessdate=21 жовтня 2024 |language=en}}</ref>

Магазин з унарним алфавітом називається '''лічильником'''. Два лічильники можуть промоделювати роботу магазину.
{{Розширити розділ|Як два лічильники можуть промоделювати роботу магазину?|дата=квітень 2010}}

=== Стековий автомат (СА) ===
Аналогічний МА, але крім цього вміє читати символи з середини стрічки.

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

== Примітки ==
{{reflist}}

== Література ==

; Українською
* {{книга
|автор        = [[Гаврилків Володимир Михайлович|Гаврилків В. М.]]
|назва        = Формальні мови та алгоритмічні моделі
|рік          = 2023
|видавництво  = Голіней
|місто        = {{Comment|І.-Ф. |Івано-Франківськ}}
|сторінок     = 180
}}

; Іншими мовами
* {{книга
 |автор        = Гэри М., Джонсон Д.
 |заголовок    = Вычислительные машины и труднорешаемые задачи
 |місто        = {{Comment|М.|Москва}}
 |видавництво  = Мир
 |рік          = 1982
 |сторінок     = 416
 }}
* {{Cinderella Book}}
* {{книга
 |автор        = Эббинхауз Г.-Д., Якобс К., Ман Ф.-К., Хермес Г.
 |заголовок    = Машины Тьюринга и рекурсивные функции
 |місто        = {{Comment|М.|Москва}}
 |видавництво  = Мир
 |рік          = 1972
 |сторінок     = 264
 }}

== Див. також ==
{{Портал|Математика}}
* [[Модифікації машини Тюрінга]]
* [[Недетермінована машина Тюрінга]]
* [[Алгоритм]]
* [[Лямбда-числення]]

== Посилання ==

* [https://web.archive.org/web/20070112192232/http://www.fcss.ukma.kiev.ua/prks-manual/tjuring.htm Навчальний проект з курсу "Основи програмування": Машина Тьюринга].

{{Comp-sci-stub}}
{{Math-stub}}

{{Математична логіка|state=collapsed}}
{{Бібліоінформація}}
[[Категорія:Алгоритми]]
[[Категорія:Теорія алгоритмів]]
[[Категорія:Теоретична інформатика]]
[[Категорія:Алан Тюрінг]]
[[Категорія:Формальні мови]]
[[Категорія:Моделі обчислень]]
[[Категорія:Винаходи Англії]]