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

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

1. Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, …. В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита

A = {L, α₁, α₂,..., α_n-1}, n ≥ 2. Пустая ячейка обозначается символом L, а сам символ L называется пустым, при этом остальные символы называются непустыми. В этом алфавите A в виде слова (конечного упорядоченного набора символов) кодируется та информация, которая подается в МТ. Машина «перерабатывает» информацию, поданную в виде слова, в новое слово.

2. Считывающая головка (некоторый считывающий элемент) перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оставаться на месте (Н). Обозначим множество перемещений (сдвига) головки D = {П, Л, Н}. Если в данный момент времени t головка находится в крайней клетке и сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка, над которой окажется головка в момент t +1.

3. Внутренняя память машины представляет собой некоторое конечное множество внутренних состояний Q = { q₀, q₁, q₂,..., q_m }, m ≥ 1. Будем считать, что мощность |Q| ≥ 2. Два состояния машины имеют особое значение: q₁ – начальное внутреннее состояние (начальных внутренних

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

1 SGzUpqJtlMapEB8TDGlgYHTjaxI1PkexmwR+PYcYYLuPR+89l+1m14kRh9B60nC7UCCQKm9bqjW8 vz3fJCBCNGRN5wk1fGKAXX55kZnU+on2OJaxFhxCITUamhj7VMpQNehMWPgeiXdHPzgTuR1qaQcz cbjr5FKptXSmJb7QmB4fGqxO5dlp2Dy9lEU/Pb5+FXIji2L0MTl9aH19Nd9vQUSc4x8MP/qsDjk7 HfyZbBCdhuVK3THKxXoFgoHfwYHTEwUyz+T/D/JvAAAA//8DAFBLAQItABQABgAIAAAAIQC2gziS /gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgA AAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgA AAAhAEUS8njgAQAA2AMAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAG AAgAAAAhAAvANfzdAAAACQEAAA8AAAAAAAAAAAAAAAAAOgQAAGRycy9kb3ducmV2LnhtbFBLBQYA AAAABAAEAPMAAABEBQAAAAA= " strokecolor="black [3040]"/>

α1

α2

α2

α3

ᴧ

q1

 

 

4. Устройство управления в каждый момент t в зависимости от считываемого в этот момент символа на ленте и внутреннего состояния машины выполняет следующие действия:

1) изменяет считываемый в момент t символ a_i на новый символ a_j (в частности оставляет его без изменений, т. е. a_i = a_j);

2) передвигает головку в одном из следующих направлений: Н, Л, П;

3) изменяет имеющееся в момент t внутреннее состояние машины q_i на новое q_j, в котором будет машина в момент времени t +1 (может быть, что q_i = q_j).

Такие действия устройства управления называют командой, которую можно записать в виде:

q_i a_i ®q_j D a_j,

 

где q_i – внутреннее состояние машины в данный момент; a_i – считываемый в этот момент символ; a_j – символ, на который изменяется символ a_i (может быть a_i = a_j); символ D есть или Н, или Л, или П и указывает направление движения головки; q j – внутреннее состояние машины в следующий момент (может быть q_i = q_j). Выражения q_ia_i и a_jDq_j называются левой и правой частями этой команды соответственно. Число команд, в которых левые части попарно различны, является конечным числом, так как множества Q\{q₀} и A конечны.

Не существует команд с одинаковыми левыми частями, т. е. если программа машины T содержит выражения q_ia_i →ajDq_j и q_ta_t →a_kDq_k, то q_i ≠ q_t или a_i ≠ a_t и D {П, Л, Н}. Совокупность всех команд называется программой машины Тьюринга. Максимальное число команд в программе равно

(n +1) ×m, где n+1=A и m +1= Q. Считается, что заключительное состояние команды q₀ может стоять только в правой части команды, начальное состояние q₁может стоять как в левой так и в правой части команды. Выполнение одной команды называется шагом. Вычисление (или работа) машины Тьюринга является последовательностью шагов одного за другим без пропусков, начиная с первого. Итак, МТ задана, если известны четыре конечных множества: внешний алфавит A, внутренний алфавит Q, множество D перемещений головки и программа машины, представляющая собой конечное множество команд.