76.Машины Тьюринга. Примеры. Функции, вычислимые по Тьюрингу.

Машиной Тьюринга Т называется тройка множеств T= <A, Q, P>, где: A=A(T)={a₀, a₁,…, a_m} – внешний алфавит машины Т (обычно a₀=0, a₁=1) Q=Q(T)={q₀, q₁,…,q_m} – алфавит внутренних состояний или внутренний алфавит машины Т.

Р = РТ = {T(i,j) | i=1,…,n; j=0,1,…,m} – программа машины Т; где Т(i,j) – команды этой программы, причем, для каждой пары (i,j) существует одна единственная команда Т(i,j), которая имеет один из видов: q_ia_j q_ka_l q_ia_j q_kR

q_ia_j q_kL

пример: рассмотрим МТ :

Т: q₁а qbR, q₁b q₂ aR, q₂а q₀, q₂b q₁L A={a,b}

Рассмотрим работу МТ над конфигурациями

1) q₁aa

… 0 0 q₁а 0 …

… 0 b a q₂ 0 …

… 0 b a q₀ 0 …

T(a,a)=ba (T: aa|- ba)

2) q₁ ab

… 0 a q₁b 0 …

… 0 b bq₁ 0 …

… 0 bq₁ b 0 …

… 0 a bq₂ 0 …

… 0 a q₁b 0 …

T не применимо к слову ab

МТ Т можно задавать при помощи таблицы переходов и диаграммы переходов.

В таблице переходов строки соответственно внутренние состояниям q_i считывающего устройства, столбец символом внешнего алфавита. В клетках таблицы правые части соответствующих команд.

Например: Пусть А={0 1 a b c} c –вспомогательный символ q₁0P(a,b)|- q₀01ⁿ0, P(a,b)-слово длины n

q₁0 -> q₅R q₂0 -> q₃1L q₄a -> 0L

q₂1 -> R q₃1 -> L q₄b -> 0L

q₂a -> R q₃a -> L q₄c -> 0L

q₂b -> R q₃b -> L q₅0 -> q₃L

q₃ -> q₀ q₃c -> q₅R q₅1 -> q₄L

q₄0 -> R q₄1 -> q₀L q₅a -> q₂R

q₅b -> R

	0	1	a	b	c
q1	q5R
q4	q31L	R	R	R
q3	q0	L	L	L	q5R
q4	R	q0L	0L	0L	0L
q5	q3L	q4L	q2R	R