Шрифт:
Итак, машина располагает двумя конечными наборами символов — величинами, записываемыми в ячейки ленты (А = (0, 1, В)), и состояниями реестра машины (Q = (I0, El, Е2, ЕЗ, Е4)). Для того чтобы машина Тьюринга функционировала, она должна следовать определенному протоколу, словно офисный служащий. Всякий раз, когда служащий выполняет свою работу, он совершает определенную последовательность действий, и после завершения одного шага он должен знать, каким будет следующий. Подобным образом каждый раз, обработав символ на ленте, машина Тьюринга должна до начала обработки следующего символа актуализировать свое состояние.
СОСТОЯНИЯ МАШИНЫ
Простой пример возможных состояний машины из повседневной жизни представляют собой программы стиральной машины. После завершения операции аппарат актуализирует свое состояние, следуя заданной программе, как правило это стандартный цикл, состоящий из замачивания, стирки, полоскания и отжима. То есть в данном случае состояния машины (стиральной) — этапы программы, выполняемые в определенный момент.
Для того чтобы машина Тьюринга могла менять состояние, используется таблица, названная таблицей переходов, которую обозначим символом Д. В соответствии с этой таблицей, используя правила перехода, или функции, машина после завершения одной операции переходит к следующей. Таким образом, обратившись к таблице, машина Тьюринга после завершения операции актуализирует свое состояние. Каждый раз, когда головка для считывания/записи находит на ленте символ, она соотносит его с символом, описывающим собственное состояние машины и указывающим, что она должна сделать далее для каждой комбинации символов. То есть в таблице представлено состояние ячейки и состояние машины, А х Q. В соответствии с этой комбинацией по таблице определяются следующее состояние Q и новый символ А, который будет записан на ленте вместо считанного, а также то, в каком направлении должно будет перемещаться устройство по ленте: вправо (П) или влево (Л). Таким образом, в самом простом виде работа машины Тьюринга определялась тремя элементами: состоянием машины Q, алфавитом А и таблицей А, в которой собирается информация о каждом завершенном шаге машины Тьюринга для выполнения следующего.
Для того чтобы понять, как функционирует машина Тьюринга, приведем простой пример с тремя состояниями Q = {Е1, Е2, ЕЗ} и лентой памяти, ячейки которой могут содержать символы А = {0, 1}. Будем считать начальное состояние 10 равным Е1, головка считывания/записи находится во второй ячейке слева от рассматриваемого участка ленты, например имеющего вид 011110. Если таблица переходов сформирована тремя таблицами ниже, по одной на каждое из состояний El, Е2 и ЕЗ, то как будет вести себя машина?
Символ ленты
Записанный символ
Переход
Следующее состояние
0
1
Л
Е2
1
0
П
ЕЗ
Символ ленты
Записанный символ
Переход
Следующее состояние
0
0
Л
ЕЗ
1
1
П
Е1
Символ ленты
Записанный символ
Переход
Следующее состояние
0
1
Л
Е1
1
0
П
Е2
Читая таблицу переходов и учитывая, что каждая операция реализуется в единицу времени (t0, t1, t2,...), получаем, что начальное положение t0 имеет следующий вид.
Согласно таблице переходов и учитывая, что машина в начальный момент времени t0 находится в состоянии Е1, символ на ленте 1, в ячейке будет записан 0, шаг в следующую ячейку справа, состояние изменится на ЕЗ.
Действия машины для следующего момента времени t1, когда она будет находиться в состоянии ЕЗ, указаны в таблице переходов. Затем, после того как головка считает в ячейке символ 1, машина перейдет в состояние Е2, в ячейке будет записан 0, шаг в следующую ячейку вправо.
После завершения предыдущей операции наступит момент времени t2. Так как машина находится в состоянии Е2 и из ячейки считывается 1, то, следуя указаниям таблицы переходов, в ячейку будет записано 1, устройство перейдет вправо, и машина изменит состояние на Е1.
Последний момент времени, t4. Машина находится в состоянии Е1, в считываемой ячейке стоит символ 1. Согласно таблице переходов, в ячейку будет записан 0, шаг вправо, переход в состояние ЕЗ.
У-МАШИНА ТЬЮРИНГА. МОЖЕТ ЛИ МАШИНА БЫТЬ УНИВЕРСАЛЬНОЙ
Одним из ограничений машины Тьюринга является то, что она ведет себя как компьютер, выполняющий единственный алгоритм, то есть способный реализовывать только одну задачу. С исторической точки зрения одной из первых машин Тьюринга стала система AGC (Apollo Guidance Computer — бортовой управляющий компьютер миссии «Аполлон»). Эта машина была главным бортовым компьютером миссий NASA, позволивших совершить доставку человека на Луну 20 июля 1969 года. Задолго до этой эпопеи, осознавая присущее его машине ограничение, Алан Тьюринг сделал расширение своей машины, назвав результат универсальной машиной Тьюринга, или у-машиной. Речь идет о машине Тьюринга, которую можно использовать в виде любой другой машины Тьюринга, то есть способной обрабатывать другие алгоритмы. Таким образом, компьютер — это пример универсальной машины Тьюринга. Еще один пример — смартфоны, или мобильные телефоны, работающие как мини-компьютер.