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

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

Пример 1. Машина Тьюринга, реализующая базовую функцию константа С_n = 0 на правой полуленте (табл. 5)

T₁ : q_í | ^{x + 1}  q_k |

Протокол T₁:

1) q_í |  q₁ # Ï;

2) q₁ |  q₁ # Ï;

3) q₁ #  q₂ # Ë;

4) q₂ #  q_k # Ñ.

d_k

Таблица 5

Текущее	Символы vt
состояние	1	#
qí	q1 # Ï	—
q1	q1 # Ï	q1 # Ë
q2	—	q1 # C

Пусть х = 3. Тогда f (3) = C₁ (3) = 0 будет получена на машине Тьюринга следующим образом:

x+1

# | | | | #  # # | | | #  # # # | |#  # # # # | # 

q₂ q₁ q₁ q₁

# # # # # #  # # # # | #

q₂ q_k

Пример 2. Машина Тьюринга, реализующая базовую функцию константа С_n = 1 на правой полуленте (табл. 6):

T₂ : q_í | ^x+1 q_k |²

Протокол T₂:

1) q_í |  q₁ # Ï;

2) q₁ |  q₁ # Ï;

3) q₁ #  q₂ | Л;

4) q₂ #  q_k | C.

_{Таблица 6}

Текущее	Символы vt
состояние	|	#
qí	q1 # Ï	qí # Ï
q1	q1 # Ï	q2 # Ë
q2	—	q1 | C

Пусть х = 3. Тогда f (3) = C₁ (3) = 1 будет получена на машине Тьюринга следующим образом:

x+1

# | | | | #  # # | | | #  # # # | |#  # # # # | # 

q_í q₁ q₁ q₁

# # # # # #  # # # # | #  # # # # | |

q₁ q₂ q_k

Пример 3. Машина Тьюринга, реализующая базовую функцию следования  (х) = х + 1 на правой полуленте (табл. 7):

T₃ : q_í | ^x+1 q_k |^(õ+1)+1

Протокол T₃:

1) q_í |  q₁ | Ï;

2) q₁ |  q₁ | Ï;

3) q₁ #  q₂ | Л;

4) q₂ #  q₂ | Ë.

5) q₂ #  q₃ # Ï;

6) q₃ |  q_k | C;

_{Таблица 7}

Текущее	Символы vt
состояние	|	#
qí	q1 | Ï	-
q1	q1 | Ï	q2 | Ë
q2	q2 | Ë	q3 # Ï
q3	qk | C	-

Пусть х = 3. Тогда f (3) =  (3) = 3+1 будет получена на машине Тьюринга следующим образом:

x+1

# | | | | #  # | | | | #  # | | | |#  # | | | | # 

q_í q₁ q₁ q₁

# | | | | #  # | | | | | #  # | | | | | #  # | | | | | 

q₁ q₂q q₂ q₂

x + 1

# | | | | | #  # | | | | | # | | | | | #  # | | | | | #

q₂ q₂ q₃ q_k