Машина Тьюринга [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.- Граф поведения машины Тьюринга
