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

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

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

1) лента машины Тьюринга бесконечна;

2) машина Тьюринга может двигаться вдоль ленты в любом направлении.

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

Формальное определение машины Тьюринга следующее.

Определение 1:Машина Тьюринга – это пять объектов , из которых:

1) - есть конечный алфавит символов, которые могут быть записаны в ячейках и являются одновременно входными и выходными: ;

2) - есть конечное множество внутренних состояний, ;

3) -функция перехода в новое состояние, она действует из в ;

4) - функция выхода, ;

5) - функция, регулирующая движение ленты, она действует из во множество .

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

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

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

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

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

Остановка машины происходит после того, как будут выданы нужные результаты.

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

- текущее состояние машины;

- считываемый из ячейки символ;

- следующее состояние машины, ;

- символ, печатаемый в ячейке, ;

- одна из команд: .

Набор строк подобного вида называют программой работы машины Тьюринга.

В этих обозначениях описанная выше машина задается так:

,

,

,

,

,

,

,

,

Программы работы машины Тьюринга содержат все известные алгоритмические моменты (циклы, ветвления).

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

Теорема: Пусть - конечный автомат. Пусть и определены основные функции для всех :

,

,

Тогда машина Тьюринга ставит в соответствие входным строкам те же выходные строки, что и автомат .

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

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

Машины Тьюринга обладают большими возможностями, чем конечные автоматы. Можно, например, описать машины Тьюринга, вычисляющие разные функции от чисел, подаваемых на вход. Стандартным представлением неотрицательного числа в машине Тьюринга является последовательность из единиц, стоящих подряд. Два таких числа отделяются нулем. Например, строка ##111011## представляет упорядоченную пару чисел (3,2). Строка ##110111101## представляет собой последовательность чисел (2, 4, 1).

Пример: Следующая машина Тьюринга складывает два неотрицательных целых числа, поданных на вход:

,

,

,

,

,

,

,

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