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

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

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

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

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

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

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

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

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

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

где VT={ai, a2,..., an} - символы внешней памяти,

Q={qo, qi, q2...., qm} - символы внутренней памяти (q0 -начальное , qi – текущее, qk –заключительное состояния),

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

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

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

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

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

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

Таблица 1.

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

Таблица 2.

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

Например,

1) qoai —>qiajD,

2) qiak —>qjaiD,

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

i) q|am—>qkanC.

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

Таблица 3.

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

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