 |
Примеры машин Тьюринга для конкретных вычислений.
|
|
|
|
1. Счетчик четности единиц.
Рис.15. МТ для счетчика четности
На рис. 15 показана МТ в начальном состоянии q 0 , при этом обозревается первый символ двоичной последовательности, которая заканчивается ограничителем B. Далее на каждом такте ГЗЧ продвигается вправо, заменяя все символы символом "0", причем смена
состояний (q 0 на q 1 и обратно) происходит всякий раз, когда ГЗЧ обнаружит единицу. Таким образом, состояние q 0 связано с четным числом обнаруженных единиц, а состояние q 1 – с нечетным. Останов МТ (переход в заключительное состояние H) происходит по достижении символа B, при этом на его место записывается "0", если число единиц
в исходной последовательности было четным, и "1", если это число было нечетным.
После завершения процесса вычислений ГЗЧ будет указывать на эту ячейку с заключительной информацией, а во всех остальных ячейках ленты будут записаны нули.
Представим работу МТ двумя способами: таблицей и графом.
Строки таблицы содержат все "пятерки", описывающие функционирование МТ.
Таблица
| qi | sj | qij | sij | dij |
| q0 | 0 | q0 | 0 | R |
| q0 | 1 | q1 | 0 | R |
| q0 | В | Н | 0 | – |
| q1 | 0 | q1 | 0 | R |
| q1 | 1 | q0 | 0 | R |
| q1 | В | Н | 1 | – |
Рис. 16. Граф счетчика четности единиц
В вершинах графа явно указан символ, обозначающий движение ГЗЧ вправо в каждом из двух состояний. Заключительное состояние обозначено на рисунке буквой H – "halt" (останов).
2. Машина Тьюринга для проверки правильности скобочных выражений.
Рекурсивное определение правильного скобочного выражения (ПСВ) было дано
в разделе 1.3. Заметим, что конечный автомат не может решить поставленную задачу для скобочного выражения произвольной длины. МТ решает задачу в общем случае, так как наличие неограниченной ленты эквивалентно неограниченному объему памяти.
|
|
|
Рис. 17. МТ для проверки скобочных выражений
Скобочное выражение заключено между левым и правым ограничителями, обозначенными символом А. В начальном состоянии автомата ГЗЧ обозревает первый символ скобочного выражения (рис. 17). Реализация вычислений представлена графом (рис. 18).
Рис. 18. Граф МТ для проверки скобочных выражений
Работа машины: сначала ГЗЧ движется вправо до первой правой скобки, заменяет ее символом X, переходит в состояние q1 и движется влево до ближайшей левой скобки, заменяет ее символом X, переходит в состояние q0 , и челночное движение повторяется.
Если машина, находясь в состоянии q1, достигает левого символа А, то печатает "0" и останавливается – скобочное выражение неправильно.
Если машина, находясь в состоянии q0, достигает правого символа А, не обнаружив больше правой скобки, то переходит в заключительное состояние q2, связанное с движением влево, и в последний раз просматривает последовательность: не осталась ли непарная левая скобка. Если по пути встретится левая скобка, то машина печатает "0" и останавливается. При достижении в состоянии q2 левого символа А, машина печатает "1" и останавливается – скобочное выражение правильно.
3.Машина Тьюринга для умножения двух чисел в унарном коде.
Действие машины представлено рисунками 19 – 21.
Рис. 19. МТ для умножения – исходное состояние
Рис. 20. МТ для умножения – результат операции
Рис. 21. Граф МТ – множительного устройства
На рис. 21 граф представлен в сокращенном виде – не показаны петли с одинаковыми числителем и знаменателем.
МТ представляет собой простой базис для описания эффективных процедур,
поскольку все шаги, регламентирующие поведение автомата, определяются четкими правилами. В современной терминологии, МТ – простой базис для описания алгоритмов и уточнения самого понятия алгоритма.
|
|
|
В приведенных выше примерах для каждого вычисления использовался свой специальный конечный автомат – так называемая конкретная машина Тьюринга. Конечный автомат в конкретных МТ играет роль алгоритма вычислений.
Можно считать, что любая МТ вычисляет некоторую функцию (заключительное содержимое ленты) от заданного аргумента (исходное содержимое ленты). В связи
с этим возникло понятие: функция, вычислимая по Тьюрингу.
Тьюринг показал, как построить универсальную машину Тьюринга (УМТ), которая интерпретирует поведение любой конкретной МТ и, следовательно, может вычислить любую функцию, которую вычисляет конкретная МТ.
УМТ имеет структуру, показанную на рис. 22.
Рис. 22. Структура УМТ
Левая часть ленты (до символа qi) имитирует ленту конкретной МТ, правая – содержит описание автомата конкретной МТ в виде пятерок.
Символ М показывает расположение ГЗЧ конкретной МТ; будем считать, что обозреваемый символ находится справа от символа М.
Пара ячеек q i, s j – зона режима, указывающая текущее состояние и текущий обозреваемый символ (на рисунке это символ "0").
Работа УМТ: УМТ начинает работу с запоминания символов qi, sj зоны режима, затем ГЗЧ движется вправо до тех пор, пока не найдет пятерку, в которой первые два символа совпадают с символами зоны режима. Найдя такую пятерку, УМТ запоминает qij, sij, dij, и ГЗЧ движется влево. Далее выполняются следующие действия:
qi: = qij, т. е. в зону режима записывается символ, обозначающий новое состояние автомата конкретной МТ;
справа от М записывается sij;
выполняется сдвиг М согласно значению dij (L или R), что соответствует передвижению ГЗЧ имитируемой машины;
запоминается новый обозреваемый символ (справа от М) и переносится
в зону режима в качестве s j.
Таким образом, зона режима оказывается обновленной, и указанные действия повторяются до останова машины.
Вариант формулировки тезиса Тьюринга: Вычислимы те, и только те, объекты, которые могут быть вычислены УМТ.
Согласно Тьюрингу, алгоритмом можно считать только ту процедуру, закодированную для МТ, которая приводит к останову машины.
|
|
|
В связи с этим возникает вопрос: существует ли универсальный распознаватель алгоритмов, т. е. МТ, которая для любой другой МТ определит, остановится последняя или нет. Этот вопрос назван в теории машин Тьюринга проблемой останова. Доказано, что проблема останова неразрешима и, следовательно, универсального распознавателя алгоритмов не существует [1]. Существуют и другие алгоритмически неразрешимые проблемы, к доказательству неразрешимости которых привлекается механизм вычислений, введенный Тьюрингом.
Простые системы (базисы) для решения проблем вычислимости создали независимо друг от друга и другие выдающиеся исследователи в области теории алгоритмов: А. Черч (математический аппарат рекурсивных функций), А. А. Марков (нормальные алгорифмы, сводящиеся к преобразованию слов в некотором алфавите), Э. Пост (механизм преобразования двоичных последовательностей, подобный МТ). Все названные системы равноценны с точки зрения их принципиальных возможностей и эквивалентны как формализмы для определения алгоритма [3].
|
|
|
