Курсовая работа: Многоголовочная машина Тьюринга

· конечное множество S, называемое множеством состояний;

· некоторое выделенное состояние s0 S, называемое начальным;

· таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа;

· некоторое подмножество F S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

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

S x A → S x A x {-1,0,1},

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

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z → A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть, выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и, что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).

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

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

Интуитивное понимание:

Интуитивное понимание машины Тьюринга таково: имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.

Полнота по Тьюрингу:

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

Пример машины Тьюринга:

Приведем пример МТ для умножения чисел в унарной системе счисления. Машина работает по набору правил, приведённых в таблице 1:

Таблица 1. Набор правил

Набор правил	Набор правил
q0*→q0R	q4a→q4aR
q01→q0R	q4=→q4=R
q0×→q1×R	q41→q41R
q11→q2aR	q4*→q51R
q21→q21L	q5^→q2*L
q2a→q2aL	q6a→q61R
q2=→q2=L	q6×→q7×R
q2×→q3×L	q7a→q7aR
q31 → q4aR	q71→q2aR
q3a→q3aL	q7=→q8=L
q3*→q6*R	q8a→q81L
q4×→q4×R	q8×→q9H

Конкретная машина Тьюринга задается перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо(R), остаться на месте(H)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Классификация машин Тьюринга:

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

Попытка классификации машин Тьюринга, предпринята В.А. Успенским и А.Л. Семеновым [1987, с. 238–243]. Следуя ей, изобразим следующую классификационную схему:

Рассмотрим подробнее многоленточную машину Тьюринга:многоленточные машины Тьюринга имеют несколько (конечное множество) лент, каждая со своей головкой, управляющему устройству доступны символы, находящиеся в ячейках, на которых расположены головки лент. Выделены две ленты: входная, с которой разрешается только читать символы, и выходная, на которую разрешается только писать символы. Остальные ленты называются рабочими. Многоленточная машина называется k-ленточной, если у нее kрабочих лент. Действие за такт работы состоит в изменении состояния управляющего устройства, изменении символов в ячейках под головками и изменении положений головок на лентах (каждая головка сдвигается не более чем на одну позицию). Это действие однозначно определяется состоянием управляющего устройства и набором символов в ячейках под головками. Если действие выполнить нельзя, машина останавливается.

При одном движении, зависящем от состояния конечного управления и сканируемого символа каждой из ленточных головок, машина может:

1) изменить состояние;

2) напечатать новый символ на каждой из сканируемых ячеек;

3) передвинуть каждую из ее ленточных головок независимо друг от друга на одну ячейку влево, вправо или оставить ее на том же месте.

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