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

Определение 3. Машина Тьюринга - это математическая модель идеализированного вычислительного устройства. Она имеет 1) ленту, разбитую на конечное число ячеек, в каждой ячейке ленты в определенный момент времени записан один из символов а0,а1,а2,...,аN. Совокупность этих символов называется входным алфавитом; 2) конечное управление, которое может находиться в каждый момент времени в каком-то одном состоянии q0, q1, q2,...,qM; 3) управляющую головку, которая может перемещаться вдоль ленты, считывать или записывать символы.

Концепция такого рода машины сложилась в середине 30-х гг. 20 в. у А. М. Тьюринга в результате произведённого им анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, то есть последовательные преобразования знаковых комплексов.

Машину Тьюринга удобно представлять в виде некоторого автоматически действующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью — лентой. Среди состояний имеются два выделенных — начальное и заключительное. Лента разделена на клетки (ячейки) и не ограничена влево и вправо. В каждой клетке ленты может быть записан любой из символов, входящих в некоторый заранее заданный перечень (ради единообразия считают, что в пустой клетке записана «пустая буква»). В каждый момент времени Машина Тьюринга находится в одном из своих состояний и, рассматривая (посредством специального устройства) одну из клеток своей ленты, воспринимает записанный в ней символ. Если в текущий момент времени Машина Тьюринга находится в не заключительном состоянии, то в следующий за ним момент: 1) она переходит в новое состояние, быть может совпадающее со старым, или заключительное; 2) в рассматриваемой клетке старый символ заменяется новым, быть может пустым или совпадающим со старым; 3) лента машины сдвигается на одну клетку влево или вправо либо остаётся на месте. Этот шаг Машина Тьюринга вполне определяется её текущим состоянием и текущим воспринимаемым символом. Таблица, содержащая полное перечисление возможных шагов данной Машины Тьюринга, называется программой этой машины.

Текущее полное описание Машины Тьюринга. даётся её конфигурацией, которая состоит из указания для данного момента следующей информации: 1) конкретного заполнения клеток ленты символами, 2) клетки, находящейся в поле зрения машины, 3) состояния, в котором машина находится.

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

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

Формальное определение базовой модели машины Тьюринга: T= (K,S, Г, d, q0, F); K - конечное множество внутренних состояний; S - входной алфавит; Г - ленточный алфавит: S: Г-{$}, $-пробел; d - команды, частичное отображение d: KхГ->Kx (Г-{$})x{L,R}, где L,R -движение влево и вправо головки; q0- начальное состояние, с него машина начинает обработку, q0cK; F - множество конечных состояний, в которых машина переходит в представляющее состояние.