Машина Тьюринга для заданной функции

[NatNiM]

Построить машину Тьюринга Поста, вычисляющую функцию f, и проиллюстрировать ее работу на примере слова А.
f(x,y,z)=max{x+y,z}, A=1*111*111.

Это пара чисел m,n

$$ M = q_1 a_0 1^n a_0 1^m a_0 $$

Программа

$$ \eqalign{ & q_1 a_0 \to q_2 R,q_2 1 \to q_2 R,q_2 a_0 \to q_3 1,q_3 1 \to q_3 R,q_3 a_0 \to q_4 L, \cr & q_4 1 \to q_5 a_0 ,q_5 a_0 \to q_6 L,q_6 1 \to q_6 L,q_6 a_0 \to q_0 a_0 \cr} $$

складывает числа, а как найти max?

[Xaositect]

NatNiM в сообщении #211070 писал(а):

а как найти max?

бегать влево-вправо, слева отделятьть по одной единичке на шаг влево, справа отделять по одной единичке на шаг вправо.
Которое из чисел раньше кончится, то будет min.
А второе - max.

[NatNiM]

Xaositect писал(а):

NatNiM в сообщении #211070 писал(а):

а как найти max?

бегать влево-вправо, слева отделятьть по одной единичке на шаг влево, справа отделять по одной единичке на шаг вправо.
Которое из чисел раньше кончится, то будет min.
А второе - max.

Так это получится, как я понимаю, 2 отдельные программы: одна вначале складывает, затем вторая определяет max?

[Xaositect]

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

[NatNiM]

Xaositect писал(а):

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

А на вход, стало быть, подавать все три числа? Как же можно одновременно их так обработать!

[Xaositect]

Давайте я напишу какой-нибудь пример.
Вот допустим.
Даны 3 числа, их все надо сложить.
Пишем сначала программу, которая складывает первые два. Только чуть-чуть отличающуюся от той, что Вы написали.
$q_1a_0\to q_2R, q_21\to q_3a_0, q_3a_0\to q_4R, q_41\to q_4R, q_4a_0\to q_51,q_51\to q_5L$
Она переводит конфигурацию $q_1a_01^na_01^na_0$ в конфигурацию $q_5a_01^{n+m}a_0$, не затрагивая того, что стоит правее.
Теперь, если мы заменим $q_5$ на $r_1$ и напишем эту программу еще раз, только с $r$ вместо $q$, то получим программу, которая сначала переводит
$q_1a_01^ma_01^na_01^ta_0$ в $r_1a_01^{m+n}a_01^t$, а потом $r_5a_01^{m+n+t}a_0$
Машины Тьюринга можно так склеивать.

[NatNiM]

Xaositect писал(а):

Давайте я напишу какой-нибудь пример.
Вот допустим.
Даны 3 числа, их все надо сложить.
Пишем сначала программу, которая складывает первые два. Только чуть-чуть отличающуюся от той, что Вы написали.
$q_1a_0\to q_2R, q_21\to q_3a_0, q_3a_0\to q_4R, q_41\to q_4R, q_4a_0\to q_51,q_51\to q_5L$
Она переводит конфигурацию $q_1a_01^na_01^na_0$ в конфигурацию $q_5a_01^{n+m}a_0$, не затрагивая того, что стоит правее.
Теперь, если мы заменим $q_5$ на $r_1$ и напишем эту программу еще раз, только с $r$ вместо $q$, то получим программу, которая сначала переводит
$q_1a_01^ma_01^na_01^ta_0$ в $r_1a_01^{m+n}a_01^t$, а потом $r_5a_01^{m+n+t}a_0$
Машины Тьюринга можно так склеивать.

ну так последнее выражение - сумма трех чисел, а не max. Или отсюда можно плясать к max?

[Xaositect]

Это пример.
Правила форума запрещают давать полные решения.
Да, отсюда можно плясать.