Примеры машин Тьюринга

Рассмотрим машины Тьюринга (МТ), исполняющие некоторые примитивно-рекурсивные функции.

Пусть V_т={|, #}.

Пример1. T₁:=вычисление функции С_n=0 на правой полуленте: q_о|^x+1#→q_k|#.

Схема работы МТ для х=3 (правая полулента):

Протокол Т₁: 1) q_о|→q₁#П,

2) q₁|→q₁#П,

3) q₁#→q₂#Л,

4) q₂#→q_k|C.

Таблица:

qÎQ	Символы VT
|	#
q0	q1#П	-
q1	q1#П	q2#Л
q2	-	qk|C

Граф:

Пример2. T₂:= вычисление функции С_n=1 на правой полуленте: q_о|^x+1#→q_k||#.

Протокол Т₂: 1) q_о|→q₁#П,

2) q₁|→q₁#П,

3)q₁#→q₂#|Л,

4) q₂ #→q_k|C.

Таблица:

qÎQ	Символы VT
|	#
q0	q1#П	-
q1	q1#П	q2|Л
q2	-	q1|C

Граф:

Пример 3. T₃:= вычисление функции λ(x)=х+1 на правой полуленте: q_o|^x+1#→q_k|^(x+1)+1#.

Протокол Т₃: 1) q_o|→q₁|П,

2) q₁|→q₁|П,

3) q₁#→q₂|Л,

4) q₂|→q₂|Л,

5) q₂#→q₃#П,

6) q₃|→q_k|C.

Таблица:

qÎQ	Символы VT
|	#
q0	q1|П	-
q1	q1|П	q2|Л
q2	q2|Л	q3#П
q3	qk|С	-

Граф: