Машина Тьюринга (алгоритм)

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

Потом делаем набросок алгоритма:

1) Найти начало второго (правого) числа
2) Запомнить первую цифру
3) Переместиться вправо на первое свободное место
4) Записать эту цифру в эту позицию
5) Повторить шаги 1-4 для остальных цифр второго числа
6) Сделать что-то похожее на 1-5 для первого (левого) числа только с учетом того, что в п. 3 нужно сперва пропустить копию второго числа, а уж потом искать первую свободную клетку.

Тут две тонкости
А) Как запомнить цифру? Это просто - будут два похожих набора команд машины, отличающихся только номерами состояний - один набор для переноса цифры 1, другой - для 0.

Б) Как найти вторую, третью и т. д цифры копируемого числа? Для этого нужно, например, скопированные числа заменять на другой символ. Например, скопированные 1 будем заменять на букву А, 0 на букву B.

Начинаем писать программу, q0 - начальное состояние. Головка слева от чисел. Символом подчеркивания я обозначу пустое значение в ячейке.
Ищем правый край второго числа:
q0_ ->q0_L
Перемещаемся к первой не скопированной цифре второго числа
q00->q10L -- если в ячейке 0 оставляем ноль, шаг влево
q01->q11L -- если в ячейке 1 оставляем 1 шаг влево
q1_->q2_R -- если в ячейке пусто - оставляем пусто возвращаемся на шаг вправо
q1A->q2AR -- если в ячейке А - оставляем А, шаг вправо
q1B->q2BR --если В - оставляем В, шаг вправо
Теперь каретка либо стоит на первой не скопированной цифре первого числа и нам нужно его "запомнить" и скопировать в первую свободную клетку слева, либо каретка стоит на пустой позиции, что означает, что она сразу натолкнулась на А или В, т. е. все цифры второго числа скопированы:

q2_->q3_L -- Переход к копированию первого числа
q21->q4AR - перешли в режим "копирование 1", заменили 1 на А
q20->q5BR - перешли в режим "копирование 0", заменили 0 на В

Теперь у нас будут две похожих ветки алгоритма, отличающихся только номерами состояний. Рассмотрим для режима "копирование 1"
Нужно вернуться к правому краю числа, пропустить одну пустую ячейку, если есть - пропустить уже скопированные цифры и вписать 1 в первую свободную ячейку:
q41->q41R
q40->q40R
q4_->q6_R
q60->q60R
q61->q61R
q6_->q71L - записали в первую свободную 1 пошли обратно.

Теперь, при движении влево нам нужно пропустить все цифры копии и вернуться к состоянию поиска первой не скопированной цифры второго числа
q70->q70L
q71->q71L
q7_->q0_L

Теперь пишем симметричный код, для копирования 0, начинающийся с q5, только там вместо q6, q7 будут q7, q9

Выполняя эту программу, рано или поздно, программа скопирует второе (правое) число, будет стоять в исходной позиции (на пустой клетке), а все цифры первого числа буду заменена на А и В.

Дальше нужно сделать похожий алгоритм для "левого" числа, только там, во первых, пока ищем начало числа, поменять А и В на 1 и 0. И при поиске начала и копировании не забывать пропустить "правое" число и его копию. Попробуйте дальше сами.

Как-то так, возможно есть вариант проще, но это надо попробовать доделать, а потом подумать, как оптимизировать. Вообще, всегда полезно потренироваться на простых задачах, "набить руку", чтобы сразу замечать похожие действия.

Попробуйте сначала на Паскале или на Си написать такой алгоритм.