Формальное определение машины Тьюринга

Машина Тьюринга [i142] это набор T = <А, Q, П>,

где А - внешний алфавит с выделенным пустым символом # или λ или a0;

Q - Алфавит внутренних состояний, с выделенными символами конечного и начального состояний q0[i143] и q1[i144];

П - программа, П: Q×А → Q×A×S.

[i145] Если машина, начав работу с некоторым словом, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. При этом слово, записанное на ленте в заключительном состоянии, считается результатом ее работы.

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

Иногда вышеприведенное определение обобщают в следующем образом.

Математическая модель машины Тьюринга имеет вид:

Т=<V_T, Q. D, ϕ, ψ, ξ >,

где V_T={a_i, a₂,..., a_n} - символы внешней памяти,

Q={q_o, q_i, q₂...., q_m} - символы внутренней памяти (q₀ -начальное, q_i – текущее, q_k –заключительное состояния),

D = {П. Л, С} - сим волы перемещения считывающей - записывающей головки (П - вправо, Л - влево, С - стоп),

ϕ[i146]: Q ⊗ V_T => V_T - функция выхода,

ψ: Q ⊗ V_T => Q - функция переходов,

ξ: Q ⊗ V_T => D - функция перемещения головки.

Описание машины Тьюринга есть последовательность символов на информационной ленте, положение считывающей – записывающей головки относительно ячейки информационной ленты и текущее состояние управляющего устройства. Такое описание называют конфигурацией машины Тьюринга:

K = α q_i β, где α - слово (или последовательность символов), расположенное слева от считывающей – записывающей головки, β - слово, расположенное под и справа от считывающей - записывающей головки; q_i — текущее состояние машины Тьюринга. Символ ‘а’, находящийся в ячейке непосредственно под считывающей - записывающей головкой, является первым символом слова β. К не заключительной конфигурации может быть применима только одна команда, которая переводит машину в новую конфигурацию. Так реализуется дискретность и детерминизм алгоритмического процесса. Для удобства анализа вычислительных алгоритмов математик Пост предложил ограничить множество символов внешнего алфавита VT[i147] двумя символами, т.е. VT[i148] = {|, #}, где "|" (палочка) есть символ унарного кода числа, а "#" (диеза или решетка) есть символ пробела между числами, представленными в унарном коде. При этом любое целое положительное число может быть записано на информационной ленте последовательностью палочек, как это представлено в таблице 1.

Таблица 1.

Для упорядочения протоколов информационную ленту ограничивают только в одну сторону, т. е. существуют левые и правые полу-ленты. В зависимости от используемой полу-[i149] ленты приняты различные схемы записи конфигураций машины Тьюринга (таблица 2).

Таблица 2.

Работу машины Тьюринга удобно описывать протоколом, таблицей и/или графом. При протокольной записи все команды должны быть записаны упорядоченным списком*[i150]. На заключительном шаге должно быть получено значение заданной функции y=f(x₁, x₂,..., x_n).

Например,

1) q_oa_i —>q_ia_jD,

2) q_ia_k —>q_ja_iD,

.................................

i) q_|a_m—>q_ka_nC.

При табличном описании каждая строка имеет имя текущего и начального состояний машины, а столбец – имя символа внешней памяти. Тогда элементами таблицы являются правые части команд q_ja_iD (смотри таблицу 3).

Таблица 3.

Табличная форма описания машины более компактна и позволяет применить матричные методы анализа для оптимизации структуры алгоритма. При описании машины Тьюринга графом вершинами являются состояния управляющего устройства, а дугами — переходы в те состояния, которые предусмотрены командой. При этом на дуге над символом «/» указывают считываемый символ[i151], а под символом «/» - записываемый символ [i152] на информационную ленту и команду на перемещение головки (смотри рисунок 2).

Рисунок 2.- Граф поведения машины Тьюринга