Машины Тьюринга

Понятие алгоритма

Рассмотрим основные требования к алгоритмам.

1°. Дискретность. Любой алгоритм состоит из отдельных шагов, на каждом из которых происходят определенные преобразования некоторой системы величин. В начале алгоритма эту систему образуют исходные данные, в конце – результаты работы алгоритма.

2°. Детерминированность. Система величин, получаемая на каждом шаге алгоритма, однозначно определяется величинами, полученными на предыдущих шагах.

3°. Элементарность шагов. Преобразования системы величин на каждом шаге алгоритма должны быть простыми и число шагов должно быть конечным.

4°. Результативность. Заключается в остановке алгоритма после конечного числа шагов с указанием того, что считать результатом.

5°. Массовость. Заключается в выборе для работы алгоритма исходных данных из потенциально бесконечного множества.

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

Такие формальные определения алгоритма были сделаны в 30-х годах XX-го века в работах сразу нескольких математиков, которые оказались различными по форме, но эквивалентными по содержанию.

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

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

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

1°. Рекурсивные функции.

2°. Машины Тьюринга.

3°. Нормальные алгорифмы А.А. Маркова.

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

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

Управляющая головка представляет собой конечный автомат с множеством внутренних состояний . В каждый момент времени она находится в одном из этих состояний и обозревает одну из клеток ленты. В зависимости от своего состояния и буквы на ленте головка записывает новую букву (в частности, ту же самую букву), переходит к следующему моменту времени в новое состояние(в частности, то же самое) и сдвигается по ленте – либо на одну клетку влево ( ), либо на одну клетку вправо ( ), либо остается на месте ( ). Среди внутренних состояний выделено одно, скажем , которое называется заключительным. Если после некоторого очередного сдвига головка попадает в заключительное состояние, то машина прекращает свою работу (останавливается).

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

1) распределение букв по клеткам ленты;

2) клетка, обозреваемая головкой;

3) состояние головки.

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

Если машина, работая в соответствие с указанными правилами, в некоторый момент времени придет в заключительное состояние, то она считается применимой к данной конфигурации (или к начальному слову, записанному на ленте). Результатом работы машины при этом считается слово, которое окажется записанным на ленте в заключительной конфигурации.

Если же при работе машины ни в какой момент времени ее головка не окажется в заключительном состоянии, то машина считается неприменимой к начальной конфигурации (и к начальному слову). Результат ее работы в этом случае не определен.

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

,

где – состояние головки; – буква в обозреваемой головкой клетке; – состояние головки в следующий момент; – буква, записываемая вместо в обозреваемую клетку; – сдвиг к следующему моменту ( , или ).

Пример 1. Машина “+1” имеет следующую систему команд:

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

Пример 2. Машина задается системой команд

Эта машина, не изменяя написанного на ленте слова, устанавливает головку против крайнего правого символа слова.

Меняя и , получим машину , выходящую на крайний левый символ слова.

Пример 3. Машина “–1” задается системой команд

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