Контрольная работа № 4

Задание 2

Пример 1 оформляем в виде:

ц (х1, х2, 0 ) = max (х1, х2 )

ц (х1, х2, y + 1 ) = max (х1, х2, 0, ц (х1, х2, y) )

Пример 2 берем новый:

ц (х, 0 ) = 2 х,

ц (х, y + 1 ) = I33 (х, y, S (ц (х, y)))

max (х1, х2, 0, ц (х1, х2, y) )

Задание 2

Для конкретных машинных слов начала и конца программы машины Тьюринга получаем:

q1 1 > q1 1 П; …; q1 1 > q1 1 П

q1 0 > q2 0 Л; …; q2 1 > q0 0

Табличный вид программы:

Q

q1

q2

A

0

q2 0 Л

q2 0

1

q1 1 П

q2 0