Лекция: Машина Тьюринга.

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

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

Предыстория её создания связана с формулировкой списка из 23 кардинальных проблем математики, представленного Давидом Гильбертом на II Международном Конгрессе математиков в Париже в 1900 году.

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

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

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

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

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

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

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

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

· записывать символ алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой);

· передвигать головку на одну ячейку влево, вправо или остается на месте;

· менять свое внутреннее состояние; (с18)

Рис.2 Машина Тьюринга

Формально машина Тьюринга может быть описана следующим образом (с19):

· конечное множество состояний – Q = {q0, q1, ..., qn}, в которых может находиться машина Тьюринга, называемое внутренним алфавитом;

· конечное множество символов ленты – А = {a0, а1, ..., аt}называемое внешним алфавитом;

· функция (функция переходов или программа), которая задает отображение пары из декартова произведения Q x А (машина находится в состоянии и обозревает символ ak) в тройку декартова произведения Q х А х {L,R,E} (машина переходит в состояние qj, заменяет символ ak на символ am и передвигается влево, вправо на один символ ленты или остается на месте) – Q x А-->Q х А х {L,R,E}:. Предполагается, что для каждой пары qiak, i=1,…n, k=0,…t имеется точно одна команда. Множество этих команд называется программой и в программе имеется n(t+1) команд;

· один символ (пустой);

· подмножество определяется как подмножество входных символов ленты, причем; т.е. в начальный момент на ленте имеется конечное число непустых символов.

· одно из состояний – является начальным состоянием машины, а заключительным.

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

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

Для МТ ниоткуда не следует, что начав работать из начального состояния, она когда-нибудь выйдет на заключительное состояние. Вводить это требование не получается, т.к. по описанию нельзя заранее предугадать эту ситуацию.

Способы задания МТ:

Список команд (с20)

Таблица переходов (с20)

Граф переходов. (с21)

Таблица переходов

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