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

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

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

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

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

Рис. 4.1.

Конечный автомат работает по тактам. На каждом такте он читает с помощью некоторой входной головки символ из обозреваемой ячейки входной ленты, изменяет свое состояние и печатает некоторый символ выходного алфавита в обозреваемую ячейку выходной ленты, после чего две его головки чтения и записи перемещаются на одну позицию вправо. Описание функционирования конечного автомата можно считать его программой: в ней просто перечислено конечное число четверок (команд) <s, a, p, y>, где s — текущее состояние, а — очередной входной сигнал, p — следующее состояние и у — очередной выходной сигнал. Программа КА — это просто перечисление аргументов и соответствующих результатов частично-определенной функции переходов и выходов автомата.

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

Машина Тьюринга работает по тактам. На каждом такте она читает символ из обозреваемой ячейки рабочей ленты, изменяет свое состояние в зависимости от своего внутреннего состояния и прочитанного символа и печатает символ в обозреваемую ячейку рабочей ленты, после чего ее головка чтения-записи может переместиться на одну позицию влево, вправо или остается на месте. Описание функционирования МТ можно считать ее программой, которая представлена конечным набором пятерок (команд) <s, a, p, y, D>, где s, а, р и у имеют тот же смысл, что и в конечном автомате, a D — направление перемещения головки по рабочей ленте, которое может быть одним из трех значений: L — влево, R — вправо и Н — оставаться на месте. Иными словами, программа МТ — это просто конечный список пятерок, представляющих собой аргументы и соответствующие им результаты частично-определенной функции переходов и выходов .

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

Рассмотрим, как работает машина Тьюринга. Конфигурацией машины Тьюринга называется ее текущее состояние, текущее состояние рабочей ленты и место расположения головки. При работе МТ в каждом такте происходит смена конфигураций. Пусть МТ находится в состоянии s и в обозреваемой ячейке ленты находится символ а. Если в программе МТ нет команды для пары <s, a>, то МТ останавливается. Если в программе МТ несколько команд для данной пары <s, a>, то это — недетерминированная машина Тьюринга, в ней выполняется одна из нескольких возможных команд с левой частью <s, a>. Очевидно, что в любой момент работы на ленте МТ находится только конечная цепочка «значащих» символов. После останова машины Тьюринга эта цепочка является результатом переработки входной цепочки. Таким образом, МТ является автоматом-преобразователем символьных цепочек.

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