5 Контрольные вопросы

1) Какие предикаты называются равносильными?

2) Как привести формулу к предваренной нормальной форме?

Практическая работа №13. Применение и конструирование машин Тьюринга.

1 Цель работы

Научиться:

- применять и конструировать машины Тьюринга;

- конструировать машины Тьюринга.

2 Теоретическая часть

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

В каждой машине Тьюринга есть две части:

1) неограниченная в обе стороны лента, разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a₀, a₁, ..., a_m}и алфавит состояний Q = {q₀, q₁, ..., q_p}. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q.) Состояние q₀называется пассивным. Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q₁ называется начальным. Находясь в этом состоянии, машина начинает свою работу.

Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит пустая буква а0 — признак того, что ячейка пуста).

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

 Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву  он видит, а также в зависимости от своего состояния   автомат может выполнять следующие действия:

• записать новую букву в обозреваемую ячейку;

• выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;

• перейти в новое состояние.

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

			…		…
…

Клетка (q_j, a_i) определяется двумя параметрами — символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен). После выполнения автоматом очередной команды он переходит в состояние q_m (которое может в частном случае совпадать с прежним состоянием q_j). Следующую команду нужно искать в m-й строке таблицы на пересечении со столбцом a_l (букву a_lавтомат видит после сдвига). Договоримся, что когда лента содержит входное слово, то автомат находится против какой-то ячейки в состоянии q1. В процессе работы автомат будет перескакивать из одной клетки программы (таблицы) в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q₀. Эти клетки называются клетками остановки. Дойдя до любой такой клетки, машина Тьюринга останавливается. Несмотря на свое простое устройство, машина Тьюринга может выполнять все возможные преобразования слов, реализуя тем самым все возможные алгоритмы.

Свойства машины Тьюринга как алгоритма

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

Дискретность. Машина Тьюринга может перейти к (к + 1)-му шагу только после выполнения к-го шага, т.к. именно к-й шаг определяет, каким будет (к + 1)-й шаг.

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

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

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

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