2 задачи по теории алгоритмов

1) Построить Машину Тьюринга, которая выполняет удвоение:

q1 011010 --> qk 01101 011010.

Запишите алгоритм таблицей и диаграммой.

Пропишите работу МТ по шагам для заданного числа

2) Докажите, что функция f(x, y)=x! (0!=1) является примитивно рекурсивной.