Головна |
a0 | a1 | a2 | |
q1 | а0Пq1 | a1Пq1 | a2Лq2 |
q2 | а1Пq2 | a2НQ0 | a0НQ0 |
Таким чином, машина Тьюринга може бути представлена ??у вигляді четвірки:
(4.9)
Робота машини Тьюринга:
Інформація, що зберігається на стрічці, є набором символів з зовнішнього алфавіту. Початковий стан керуючої головки характеризується символом внутрішнього алфавіту . Робота машини складається з тактів. Протягом будь-якого такту машина Тьюринга здійснює такі дії: машина Тьюринга знаходиться у внутрішньому стані , зчитує вхідний символ і по таблиці роботи здійснює операцію зсуву , переходячи в стан , При цьому вхідний слово замінюється на :
Якщо в результаті операції машина перейде в стан , То робота машини зупиняється. якщо стан недосяжно, то значить у даній вхідному слову машина Тьюринга не досягає кінцевого стану і алгоритму для даного вхідного слова не існує.
ПРИКЛАД
Побудувати машину Тьюринга, яка буде прати останню одиницю в послідовності одиниць.
Зовнішній алфавіт - . Внутрішній алфавіт - , При цьому стан .сохраняется до тих пір, поки не буде знайдений кінець послідовності одиниць, стан - Стирання останньої одиниці. При цьому слід зауважити, що ситуація в роботі машини Тьюринга неможлива, тому відповідна клітинка Довизначивши довільно, наприклад . Початковий стан на початку послідовності одиниць. Робоча програма машини Тьюринга має вигляд:
Перевіримо працездатність машини Тьюринга:
1.
2.
3.
4.
5.
Теза А. Черча. якщо функція здійсненна, То вона завжди може бути представлена ??у вигляді машини Тьюринга.
Алгоритм Магу для визначення безлічі зовнішньої стійкості. | Безліч шляхів у графі | Алгоритм фронту хвилі. Пошук мінімального шляху в графі. | Алгоритм фронту хвилі. | Алгоритм приведення графа до ярусно-паралельній формі. | Дерева і ліси | Алгоритм отримання дерева з графа | ТЕОРІЯ АЛГОРИТМІВ | Функція-проекція | Правило примітивної рекурсії |