Програма для машини Тьюрінга

Сама по собі МТ нічого не робить. Для того щоб змусити її працювати, треба написати для неї програму. Ця програма записується у вигляді таблиці, в якій рядки відповідають станам, а стовпці відповідають символам. Які саме символи і стани вказувати в таблиці визначає автор програми. В комірках таблиці вказуються ті такти, які повинна виконати каретка, коли вона перебуває у відповідному стані і розпізнає на стрічці відповідний символ. Наприклад, команда R в таблиці буде записана наступним чином:

Q      A			...
		R
...

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

На практиці частіше використовують скорочену таблицю. Скорочення полягають в наступному:

а) якщо стан машини після виконання команди не змінюється, то він другий раз вже не записується;

б) якщо команда записує в комірку ту саму букву, що й була записана там, то ця буква другий раз вже не записується.

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

 Наприклад: 

Табличне представлення	Скорочена таблиця
Q    A	Q    A

Правила виконання програми

До виконання програми потрібно проробити наступні попередні дії.

По-перше, треба записати на стрічку вхідне слово, до якого буде застосована програма. Вхідне слово - це кінцева послідовність символів, записаних у сусідніх комірках стрічки; усередині вхідного слова не повинно бути порожніх комірок, а зліва і справа від нього повинні бути тільки порожні комірки (зазначені в таблиці першим стовпцем). Порожнє вхідне слово означає, що всі комірки стрічки порожні.

По-друге, треба встановити каретку в початковий стан  (зазначений в таблиці першим рядком) і розмістити його під першим символом вхідного слова: 

Якщо вхідне слово порожнє, то каретка може вказувати на будь-яку комірку, тому що всі вони порожні.

Після цих попередніх дій починається виконання програми. У таблиці відшукується комірка на перетині першого рядка (тому що каретка перебуває в початковому стані ) і того стовпця, що відповідає першому символу вхідного слова, і виконується такт, записаний у цій комірці. В результаті каретка опиниться в новій конфігурації. Тепер такі ж дії повторюються, але вже для нової конфігурації: у таблиці відшукується комірка, що відповідає стану і символу цієї конфігурації, і виконується такт із цієї комірки. І так далі.

Коли завершується виконання програми? Будемо позначати стан зупинки через . Такт, що містить  стан зупинки називається тактом зупинки. Потрапивши в нього, машина припиняє роботу.

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

Нехай задана послідовність конфігурацій К₀ => К₁ => К₂ => ... =>К_p , де К₀ - початкова конфігурація, К_p - кінцева конфігурація. Така послідовність конфігурацій називається протоколом. Будемо говорити, що вхідне слово  переробляється машиною в вихідне слово , якщо від слова , що знаходиться в початковому положенні, машина після виконання кінцевого числа команд приходить до слова , що знаходиться в кінцевому положенні, тобто в положені зупинки.

В цілому можливі два результати роботи МТ над вхідним словом:   

1) Перший результат - «гарний»: це коли в якийсь момент МТ зупиняється (попадає на такт зупинки). В такому випадку говорять, що МТ може бути застосована до заданого вхідного слова. А то слово, що на цей момент отримано на стрічці, вважається вихідним словом, тобто результатом роботи МТ, відповіддю.

В момент останова повинні бути виконані наступні обов'язкові умови:

 - всередині вихідного слова не повинно бути порожніх комірок (хоча в процесі виконання програми всередині слова порожні комірки можуть бути, але в кінці їх вже не повинно залишитися);

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

  2) Другий результат - «поганий»: це коли МТ зациклюється, ніколи не потрапляючи на такт зупинки (наприклад, каретка на кожному кроці переміщується вправо і не може зупинитись, тому що стрічка нескінченна). В цьому випадку говорять, що МТ не може бути застосована до заданого вхідного слова.

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

На яких вхідних словах алгоритм повинен зупинятися? На, так званих, гарних словах, тобто на таких, які відносятся до допустимих вхідних даних задачі, для яких задача є змістовною. Але на стрічці можуть бути записані будь-які вхідні слова, у тому числі й ті, для яких задача не має змісту; на таких словах поводження алгоритму не фіксується, він може зупинитись (при будь-якому результаті), а може і зациклитися.