25 Машина Тьюринга (мт). Формальное представление. Принципы функционирования. Языки мт. Понятие останова мт.

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

Тезис Черча-Тьюринга:

Любое разумное определение алгоритма, предложенное в будущем, будет эквивалентно уже известным определениям.

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

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

Формальное описание

М=(Q, ∑, Г, δ, q₀, B_, F), причем ∑ принадлежит Г

δ = δ(q, x)= (p, γ, D), p принадлежит Q, γ принадлежит Г

D=R/L || |

Для формального описания работы машины Тьюринга, вводится понятие мгновенного описания MOj=X₁… X_i-1q X_i… X_n Используется отношение |--

Пусть δ(q, x)= (p, γ, L) ,т.е. головка сдвигается влево. Тогда

Х₁Х₂…Х_i-1qХ_iХ_i+1…Х_n|-- Х₁Х₂… Х_i-2pХ_i-1YХ_i+1…Х_n

Если i=1, то М переходит к пробелу слева от Х₁. В этом случае

qХ₁Х₂…Х_n|-- pBYХ₂…Х_n

Если i=n и Y=B, то

Х₁Х₂… Х_n-1qХ_n|-- Х₁Х₂… Х_n-2pХ_n-1

Пусть δ(q, x)= (p, γ, R) ,т.е. головка сдвигается вправо. Тогда

Х₁Х₂…Х_i-1qХ_iХ_i+1…Х_n|-- Х₁Х₂… Х_i-1pYpХ_i+1…Х_n

Если i=n, то

Х₁Х₂…Х_n-1qХ_n|-- Х₁Х₂… Х_n-1YpB

Если i=1 Y=B, то

qХ₁Х₂…Х_n|-- pХ₂…Х_n

Существует понятие “Допустимости” для МТ – допустимость по останову. МТ останавливается, если попадает в состояние q, обозревая ленточный символ Х, и в этом положении нет переходов

26 Модификации мт. Память в состоянии. Многодорожечная мт. Подпрограммы.

Конечное управление, входящее в состав МТ, можно использовать не только для представления позиции в программе, но и для хранения конечного объема информации. Использование этой идеи и многодорожечной ленты показано на рисунке. Здесь КУ содержит не только управляющее состояние q, но и три элемента данных А, В, С. Состояние [q, А, В, С] просто рассматривается в виде кортежа, что позволяет описывать переходы более систематично.

Еще одним из полезных приемов является представление ленты МТ как образованную несколькими дорожками. Каждая дорожка может хранить 1 символ (в одной клетке) и алфавит состоит из кортежей, с одним компонентом для каждой “дорожки”. Например, клетка обозреваемая головкой содержит символ [X, Y, Z]. Данная модификация МТ не расширяет возможностей базовой модели.

МТ – это программы, и их полезно рассматривать как построенные из набора взаимодействующих компонентов, или “подпрограмм”. Подпрограмма МТ представляет собой множество состояний, выполняющее некоторый полезный процесс. Это множество содержит стартовое состояние и состояние возврата, не имеющее переходов. Вызов подпрограммы возникает везде, где есть переход в ее начальное состояние.