Использование машины Тьюринга при алгоритмическом анализе

Использование машины Тьюринга при алгоритмическом анализе

Машина Тьюринга (далее МТ) представляет собой автомат с конечным числом состояний и неограниченной памятью, представленной бесконечной лентой (в общем случае набором лент). Лента поделена на бесконечное число ячеек, и на ней выделена стартовая ячейка.

В каждой ячейке ленты может быть записан только один символ из некоторого конечного алфавита , где предусмотрен символ для обозначения пустой ячейки.

На ленте имеется головка чтения-записи, и она подсоединены к «управляющему модулю» МТ -- автомату с конечным множеством состояний .

Имеется выделенное стартовое состояние и состояние завершения .

Перед запуском МТ находится в состоянии , а головка позиционируется на нулевой ячейке ленты.

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

1) посылает головке символ для записи в текущую ячейку каждой ленты;

2) посылает головке одну из команд «LEFT», «RIGHT», «STAY»;

3) выполняет переход в новое состояние (которое, впрочем, может совпадать с предыдущим).

На рисунке 1 представлена схема машины Тьюринга.

Машина Тьюринга -- это набор

· - алфавит, - пустой символ;

· - конечное множество состояний, , - выделенные состояния : запуск машины и завершения работы;

· - произвольные отображения:

- задает новое состояние,

-символ для записи на ленте,

- определяет перемещение головки.

Таким образом, машина Тьюринга задается таблицей команд размером , задающей правила работы машины в соответствии с функциями . Если к словарю А добавить пустой символ , то получим расширенный словарь .

Под входом для МТ подразумевается слово состоящее из символов словаря , записанного справа от стартовой позиции на ленте МТ. Договоримся, что входное слово не содержит пустых символов - иначе возникнут технические сложности, как определить, где кончается входное слово и т.п.

Результатом работы МТ над некотором входном слове X считается слово, записанное на ленте после остановки МТ.

Таким образом память МТ - конечное множество состояний (внутренняя память) и лента (внешняя память).

Данные МТ - слова в алфавите машины. Через обозначим исходное слово.

Элементарные шаги машины - считывание и запись символов, сдвиг головки на ячейку вправо, влево, на месте, а также переход управляющего устройства в следующее состояние.

«Программа управления» МТ это задание записанное системой правил (команд) вида:

( - направление сдвига головки )

«Программу управления» можно задать таблицей, строки которой соответствуют состояниям МТ, столбцам - входные символы, а на пересечении строки и столбца записана тройка символов .

Альтернативным способом описания «программы управления» является диаграмма переходов, представленная в виде ориентированного графа, вершинами которого являются состояния , дуги помечены переходами вида .

Полное состояние МТ, по которому однозначно можно определить ее дальнейшее поведение, определяется ее внутренним состоянием, состоянием ленты и положением головки.

Пример 1. Сложение. Рассмотрим задачу сложения 2 натуральных чисел. Договоримся представлять натуральные числа в единичном (унарном) коде , например, для числа х справедливо: . Положим, что для всех числовых функций либо .

Тогда числовая функция правильно вычислима по Тьюрингу, если существует машина Т такая, что , когда и Т работает бесконечно, начиная с , когда не вычислима.

Рассмотрим сложение 2 чисел a и b () это слово необходимо переработать в , т.е. удалить разделитель и сдвинуть одно из слагаемых, скажем первое, к другому.

Это преобразование осуществляет машина с 4 состояниями и следующей системой команд:

В табличной форме программа управления выглядит так

Диаграмма переходов описывается графом, представленном на рисунке 2.

Универсальная машина Тьюринга

Систему команд машины Тьюринга можно интерпретировать и как описание работы конкретного механизма, и как программу, управляющей работой механизма МТ. Обе интерпретации используют на практике.

Для современного инженера это обстоятельство вполне естественно. Он хорошо знает, что любой алгоритм управления может быть реализован либо аппаратурно - построением соответствующей схемы, либо программно - написанием программы для универсальной управляющей ЭВМ.

В одном случае МТ «запаивается» в электронную схему (часто такой подход применяется в военной технике). Во втором случае мы имеем дело с привычной практикой - разработки приложений на ЭВМ.

Интуитивно понятно, что правильная система команд МТ, если не делать ошибок, однозначно приводит к конечному результату. Это по существу уверенность в существовании алгоритма воспроизведения работы исполнительного механизма машины Тьюринга.

Словесное описание алгоритма может быть неточным, поэтому описание алгоритма работы МТ необходимо сделать с помощью машины Тьюринга, т.е. поставить задачу построения МТ, реализующей алгоритм воспроизведения работы исполнительного механизма МТ.

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

· Построить машину Тьюринга U, вычисляющую функцию от двух переменных, и такую, что для любой машины T с системой команд , справедливо , если определена и не останавливается, если не останавливается.

Любую МТ U, обладающую указанными свойствами называют универсальной машиной Тьюринга.

Функция является вычислимой, если существует такая машина Тьюринга T, что если на вход ей подать представленный в некоторой кодировке x, то

1) если функция f определена на x, и f(x) = y, то машина T останавливается на входе x, и на выходе у нее записано y;

2) если функция f не определена на x, то машина T зацикливается (не останавливается за любое конечное число шагов) на входе x.

Со времени первого определения понятия алгоритма было предложено множество различных универсальных моделей вычислений, зачастую весьма далеких от машин Тьюринга, однако никому еще не удалось предъявить пример процесса, который можно было бы признать алгоритмическим, но который невозможно было бы смоделировать на машине Тьюринга.

Иными словами, любой вычислительный процесс может быть смоделирован на подходящей машине Тьюринга. Это так называемый тезис Тьюринга разделяется большинством специалистов.

Тезис Тьюринга. Всякую вычислимую функцию (алгоритм) можно реализовать с помощью машины Тьюринга.

Таким образом, если мы принимаем этот тезис, то можем смело говорить о вычислимости, не указывая конкретную модель Сразу возникает вопрос: любую ли функцию y = f(x), можно вычислить на МТ?

Ответ на этот вопрос утвердительный. Существует проблема остановки алгоритма.

В общих чертах она сводится к вопросу существует ли алгоритм , который для произвольного алгоритма A и данных определял бы приведет ли работа алгоритма A к результату или нет, т.е. , если результативен и в противном случае.

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

Теорема 1. Не существует машины Тьюринга , решающей проблему остановки для произвольной машины Тьюринга T.

Полное доказательство теоремы будет приведено в курсе лекций «Математическая логика и теория алгоритмов» здесь же приведем некоторые неформальные соображения.

Пусть существует машины Тьюринга , решающая проблему остановки для произвольной машины Тьюринга T. Однако она не способна решить эту проблему для самой себя. Следовательно необходимо построить МТ , которая решала бы проблему остановки МТ . Нетрудно представить, что потребуется построить бесконечную последовательность МТ для решения проблемы остановки, что практически невозможно сделать.

Приведем примеры некоторых неразрешимых проблем (вычислимости функции).

1. Проблема остановки машины Тьюринга на пустом слове неразрешима.

2. Нет алгоритма, который для заданной машины Тьюринга T и ее состояния qk выясняет: попадет ли машина в это состояние хотя бы для одного входного слова x .

При истолковании утверждений, связанных с алгоритмической неразрешимостью, следует иметь в виду, что здесь речь идет об отсутствии единого алгоритма решения проблемы. При этом не исключена возможность решения этой задачи в частных случаях, но различными средствами для каждого случая.

Список литературы

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений. 2008

2. Коварцев А.Н. Автоматизация разработки и тестирования программных средств. - Самара, СГАУ. 2005 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - м.: Энергоатомиздат, 2008 г.

4. Немировский А.С., Юдин Д.Б. Сложность и эффективность методов оптимизации. М.: Наука, 2002