Основные определения.

Вступление.

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

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

Это воображаемая «машина» (в кавычках потому, что она вовсе не похожа на реальную машину с множеством деталей из металла, пластмассы или других материалов) — машина «на бумаге» или математическая модель машины.

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

Основные определения.

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

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

Во-вторых, машина Тьюринга снабжена потенциально бесконечной памятью. Что значит «потенциально бесконечная память»? Это значит, что хотя в каждый момент ее память хранит лишь конечное количество информации, однако для этого количества информации нет никакой верхней границы. Вообразим такую память машины Тьюринга в виде ленты, разделенной на клеточки — ячейки памяти, — которая может быть продолжена вправо сколько угодно (рис.).

В каждой ячейке может храниться только один знак из конечного множества знаков, называемого алфавитом машины Тьюринга, эти же знаки называются буквами алфавита. Ячейка может оказаться и пустой. Ради удобства договоримся: когда ячейка пустая, считать, что в ней хранится специальная буква алфавита, которую мы обозначим через s₀ и назовем пустой буквой. Таким образом, в каждой ячейке ленты в любой данный момент находится одна и только одна буква алфавита А = {s₀, s₁, s₂,...,s_k}, причем только конечное число ячеек заполнено буквами из А, отличными от пустой буквы s₀.

Машина Тьюринга снабжена (в нашем воображении) управляющей головкой, которая в каждый момент обозревает (воспринимает) лишь одну ячейку памяти и может изменить информацию, находящуюся в ней. Представить это можно следующим образом: если в какой-то момент букву в обозреваемой ячейке нужно заменить другой, то старая буква стирается и в ячейку вписывается новая (так же, как на магнитофонной ленте при новой записи автоматически стирается старая запись). Если эту операцию записать в общем виде «s_i®s_j», т. е. буква s_i заменена буквой s_j, то можно выделить следующие частные случаи:

а) i = j, т. е. буква в //////ейку вписана буква s_j, и б₂) если j = 0, то стерта буква s_i в обозреваемой ячейке.

Управляющая головка за один такт работы машины может также передвинуться влево и воспринимать соседнюю слева ячейку (этот сдвиг головки будем обозначать через Л), управляющая головка может передвинуться вправо и воспринимать соседнюю справа ячейку (этот сдвиг мы обозначим через П), управляющая головка может остаться на месте и воспринимать ту же ячейку (этот «сдвиг» обозначим через Н). На рисунке изображен фрагмент ленты, а также управляющая головка. В обозреваемой ячейке хранится буква s_i.

Машина Тьюринга имеет конечное множество внутренних состояний: Q = {q₀, q₁, q₂, …, q_m}. В каждый данный момент времени машина Тьюринга находится в одном из своих внутренних состояний. После выполнения очередного такта работы машина может изменить свое внутреннее состояние и воспринимать ячейку в следующий момент уже в новом состоянии. Разумеется, внутреннее состояние может остаться и прежним. Если машина в какой-то момент времени попадет в состояние q₀, то ее работа заканчивается (состояние q₀ называется пассивным). Из множества Q выделим еще одно состояние — q₁ — начальное состояние. В этом состоянии машина всегда начинает свою работу.

Что умеет воображаемая машина?

За один такт работы она может:

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

2) совершить сдвиг влево или вправо на одну ячейку или остаться на месте и

3) изменить свое внутреннее состояние.

И больше машина Тьюринга ничего не умеет делать.

 

Может показаться, что это очень мало. В действительности, это очень много.

Порядок работы машины Тьюринга с алфавитом A={s₀, s₁, s₂, …, s_k} и множеством состояний Q = {q₀, q₁, q₂,..., q_m} полностью определяется программой, представляющей собой таблицу, содержащую k+1 столбец и m строк. В клетке таблицы на пересечении i-го столбика (i=0, 1, 2,..., k) и j-й строки (j=1, 2,..., m) вписана команда, которую должна выполнить машина Тьюринга.

Таблица 1

Если машина в какой-то момент воспринимает управляющей головкой ячейку, в которой записана буква s_i, и машина находится в состоянии q_j, команда будет записываться в виде трехбуквенного слова s_hTq_p, где ТÎ{Л, Н, П}, т. е. обозначает один из сдвигов управляющей головки.

 

Для выполнения команды машина проделывает следующую работу:

1) буква s_i, находящаяся в обозреваемой ячейке, меняется на s_h;

2) управляющая головка совершает сдвиг Т, т. е. Л, Н или П;

3) машина переходит в состояние q_p.

 

Работа машины состоит из тактов, выполняемых в строгом соответствии с программой. Если в какой-то момент времени машина приходит в состояние q₀, то работа машины заканчивается. Программа полностью определяет работу машины, поэтому можно сказать, что машина Тьюринга задана, если задана ее программа.