Построить машину Тьюринга для вычисления арифметической функции f

Принимаю следующие соглашения:
внутренний алфавит (алфавит состояний) МТ обязательно содержит символы q0 и q1 — конечное и начальное состояния. В состоянии q1 МТ начинает работу, в состоянии q0 — заканчивает;
начальная конфигурация МТ — находясь в состоянии q1 МТ обозревает крайнюю правую непустую ячейку, т.е.НК=…0αq10⋯, где , — слово во внутреннем алфавите; конечная конфигурация МТ — …q0α'0…, где ', — слово во внутреннем алфавите, т.е. в КК МТ в состоянии q0 обозревает первую (считая слева) пустую ячейку;
всякая команда МТ имеет вид aiqj→amqnL|R|E, где L — движение на одну ячейку влево, R — аналогично вправо и E — без движения, am может совпадать с ai, а qn — c qj.
Поскольку 0 задействован для пустой ячейки, а других символов кроме 0 и 1 нет, то значение аргумента ноль — отсутствие 1, если оба аргумента равны нулю — пустая лента.
Итак, в начальной конфигурации лента МТ имеет вид:
…01…1x01…1y0…,
если один из аргументов равен нулю то картина такая:
…01…1x или y0…,
если же оба аргумента равны нулю то:
…0…0…
Работу МТ можно описать так:
1) если в начале работы, находясь в состоянии q1 МТ обозревает ячейку с 0, то оба аргумента равны нулю, их сумма равна нулю, остаток от деления на 2 равен нулю, поэтому МТ сразу, ничего не делая, заканчивает работу;
2) если в начале работы, находясь в состоянии q1 МТ обозревает ячейку с 1, то по крайней мере один из аргументов отличен от нуля, МТ должна дойти до первого 0 слева и проверить, отличен ли от нуля другой аргумент, если он равен нулю, то сумма равна имеющемуся аргументу и МТ сразу переходит к нахождению остатка от деления на 2;
3) если оба аргумента отличны от нуля, то требуется найти их сумму, для этого разделяющий аргументы 0, заменяется на 1, крайняя левая 1 заменяется на 0, после чего МТ переходит к нахождению остатка от деления на 2;
4) остаток от деления на 2 находится следующим образом — МТ двигается вправо, заменяя 1 на 0 и циклически меняя состояния между двумя, выделенными для этой цели, в зависимости от того в каком из этих двух состояний МТ попадёт на крайний справа 0 и зависит остаток от деления на 2 — ноль или единица.
0q1→0q0E — оба аргумента равны нулю, остаток от деления суммы аргументов на 2 равен 0
1q1→1q2L — хотя бы один аргумент отличен от нуля, МТ ничего не меняя двигается влево
1q2→1q2L — МТ ничего не меняя двигается влево
0q2→0q3L — МТ дошла до 0 слева, требуется проверить, отличен ли от нуля другой аргумент
0q3→0q4R — другой аргумент равен нулю, МТ сдвигается вправо, пропуская 0
0q4→0q7R — МТ переходит к нахождению остатка от деления на 2
1q3→1q5R — первый (теперь это можно утверждать) аргумент отличен от нуля МТ ищет сумму
0q5→1q6L — МТ заменяет 0, разделяющий аргументы на 1
1q6→1q6L — МТ двигается влево ничего не меняя
0q6→0q5R — МТ дошла до 0 слева от первого аргумента
1q5→0q4E — МТ удаляет 1, на ленте остаётся сумма х и у, МТ начинает поиск остатка от деления на 2
1q7→0q8R — МТ двигается вправо, удаляя 1 и циклически меняя состояния q7 и q8
1q8→0q7R — МТ двигается вправо, удаляя 1 и циклически меняя состояния q7 и q8
0q7→0q0E — остаток от деления на 2 равен нулю, МТ прекращает работу, оставляя ленту пустой
0q8→1q0L — остаток от деления на 2 равен 1, МТ прекращает работу, записывая на ленте 1
Проверим работу МТ при различных значениях аргументов:
а) оба аргумента нулевые — сумма 0, остаток от деления на 2 — 0
000 q1 →000 q0 ;
б) один ненулевой чётный аргумент
0110 q1 ⟹0110 q2 ⟹00110 q2 ⟹000110 q3 ⟹00110 q4 ⟹
⟹0110 q7 ⟹0010 q8 ⟹0000 q7 ⟹000 q0 .
в) один ненулевой нечётный аргумент
01110 q1 ⟹01110 q2 ⟹01110 q2 ⟹001110 q2 ⟹
⟹0001110 q3 ⟹001110 q4 ⟹01110 q7 ⟹0110 q8 ⟹
⟹0010 q7 ⟹000 q8 ⟹0010 q0 .
г) два ненулевых аргумента, сумма чётная
0110110 q1 ⟹0110110 q2 ⟹0110110 q2 ⟹
⟹0110110 q3 ⟹0110110 q5 ⟹0111110 q6 ⟹
⟹0111110 q6 ⟹00111110 q6 ⟹0111110 q5 ⟹
⟹0011110 q4 ⟹011110 q7 ⟹01110 q8 ⟹0110 q7 ⟹
⟹010 q8 ⟹000 q7 ⟹000 q0 .
д) два ненулевых аргумента, сумма нечётная
010110 q1 ⟹010110 q2 ⟹010110 q2 ⟹010110 q3 ⟹
⟹010110 q5 ⟹011110 q6 ⟹0011110 q6 ⟹
⟹0011110 q5 ⟹0001110 q4 ⟹01110 q7 ⟹0110 q8 ⟹
⟹010 q7 ⟹000 q8 ⟹0100 q0 .
q1
11L
q2
00L
q3
00R
q4
10E
q5
01L
q6
q7
10R
q8
q0
11L
11L
11R
00R
00R
00E
01L
10R
00E
q1
11L
q2
00L
q3
00R
q4
10E
q5
01L
q6
q7
10R
q8
q0
11L
11L
11R
00R
00R
00E
01L
10R
00E