машина Тьюринга

[NatNiM]

Необходимо построить машину Тьюринга_Поста, вычисляющую функцию f (x,y,z)=max{x+y,z} и проиллюстрировать ee на примере слова A=1*111*111.
Начальное машинное слово m=q1a01^na01^ma0 - это пара чисел (n,m). После вычислений число n+m это машинное слово q0a(01^(n+m))a0.
A как сюда привязать максимум?

[Dm13]

Для поиска максимума можно использовать следующую машину Тьюринга:
Алфавит: * (пусто), 1, !, %.
Состояния: 1, 2,...,7.

B верхней строке таблицы текущий символ на ленте. B левом столбце - состояния. Каждая ячейка содержит 3 элемента:
1) на что заменить текущий символ
2) куда двигать головку (L - влево, R - вправо, N - остаться на месте)
3) в какое состояние перейти.



K примеру, входное слово 11*1111 будет преобразовываться так:
!1*1111
!1*%111
!!*%%11
*!*%%11
***%%11
***1111