Описание машины Тьюринга

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

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

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

Q={q₁,q₂....,q_m} - символы внутренней памяти,

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

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

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

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

Описание машины Тьюринга складывается из следующих составляющих:

· последовательности символов на информационной ленте,

· положения считывающей–записывающей головки относительно ячейки информационной ленты,

· текущего состояния управляющего устройства.

Такое описание называют конфигурацией машины Тьюринга:

K = αq_iβ,

где a - слово (или последовательность символов), расположенное слева от считывающей – записывающей головки,

β- слово, расположенное под и справа от считывающей - записывающей головки;

q_i — текущее состояние машины Тьюринга.

Символ, находящийся в ячейке непосредственно под считывающей записывающей головкой, является первым символом слова β. К не заключительной конфигурации может быть применима только одна команда, которая переводит машину в новую конфигурацию. Так реализуется дискретность и детерминизм алгоритмического процесса.

Для удобства анализа вычислительных алгоритмов математик Пост предложил ограничить множество символов внешнего алфавита V_T двумя символами, т.е. V_T={|, #}, где "|" есть символ унарного кода числа, а "#" есть символ пробела между числами, представленными в унарном коде. При этом любое целое положительное число может быть записано на информационной ленте последовательностью палочек, как это представлено в таблице:

Nbsp; i …|=|i+1 Для упорядочения протоколов информационную ленту ограничивают только в одну сторону, т. е. существуют левые и правые полуленты. В зависимости от используемой полуленты приняты различные схемы записи конфигураций машины Тьюринга: Стандартная конфигурация Информационная полулента правая левая Начальная q0|x1+1#|x2+ 1#...#|xn+ 1 |x1+1#|x2+ 1#...#|xn+1q0 Конечная qk|y |yqk Работу машины Тьюринга удобно описывать протоколом, таблицей и/или графом. При протокольной записи все команды должны быть записаны упорядоченным списком. На заключительном шаге должно быть получено значение заданной функции y=f(x1, x2,..., xn). Пример протокольного описания: 1) q0aiÞqlapD …….. f) qiajÞqharD …….. i) qtauÞqkavD При табличном описании каждая строка имеет имя текущего и начального состояний машины, а столбец – имя символа внешней памяти. Тогда элементами таблицы являются правые части команд qjaiD: Состояние Символы VT ai ak … am qn qiajD … … … qi … qjaiD … … … … … … qi … … … qkanC Табличная форма описания машины более компактна и позволяет применить матричные методы анализа для оптимизации структуры алгоритма. При описании машины Тьюринга графом вершинами являются состояния управляющего устройства, а дугами — переходы в те состояния, которые предусмотрены командой. При этом на дуге над символом «/» указывают считываемый символ, а под символом «/» - записываемый символ на информационную ленту и команду на перемещение головки: