Тьюринг. Компьютерное исчисление - Рафаэль Лаос-Бельтра

Итак, что представляет собой машина Тьюринга? Из каких частей или компонентов она состоит? А-машина — это абстрактное устройство, не имеющее реального прототипа и представляющее собой простейший компьютер. Она способна считывать и записывать символы на ленте, разделенной на ячейки. Теоретически эта лента бесконечна, то есть не имеет края ни справа, ни слева. Очевидно, что она представляет собой основную память; в современном компьютере эквивалентом можно считать оперативную память — RAM (ОЗУ, оперативное запоминающее устройство). Интересно отметить, что Тьюринг посчитал бесконечную ленту необходимой для компьютера, предваряя этим возникновение одного из важнейших элементов — памяти. По очевидным причинам память компьютера не может быть бесконечной, и этим объясняется «зависание» техники, когда ее памяти недостаточно для выполнения определенной программы или операции.

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

Представим себе машину Тьюринга в самой элементарной конфигурации. С одной стороны, ей необходима головка для считывания и записи, с помощью которой считывается содержимое ячейки, а затем стирается и записывается новый символ. В общей модели машины Тьюринга считалось, что после завершения цикла чтения ячейки, стирания содержимого и записи нового символа головка и вместе с ней вся машина сдвигается по отношению к ленте на одну позицию вправо (П) или влево (Л). То есть можно представить, что лента или машина переходит к позиции П или Л. Также машине необходим небольшой объем памяти — реестр, в котором хранится информация о состоянии или конфигурации в определенный момент времени. Реестр похож на светофор, который может быть красным (К), желтым (Ж) или зеленым (3). В конкретный момент времени машина находится в определенном состоянии, и количество возможных состояний является конечным. Обозначим его множество буквой Q (см. рисунок). Представим, что наша машина находится в одном из четырех состояний: E1, Е2, ЕЗ или Е4. Также имеется начальное состояние 10, соответствующее записи в реестре при запуске машины в работу.

Итак, машина располагает двумя конечными наборами символов — величинами, записываемыми в ячейки ленты (А = (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 имеет следующий вид.