Машина тьюринга. как будет выглядеть программа умножения на 2

Влюбом случае, можно просто реализовать на машине тьюринга, это и будет доказательством. а вообще, вот понятная реализация для десятичной системы (взято с cyberforum): q0 -конечное состояние p - пустой символ l - в лево r - в право n - стоим q1 - начальное состояние 1. бежим в конец числа: q1 n-> q1 nr q1 p-> q2 pl где n от 0 до 9 2. числа от 0 до 4 можно просто умножить, без запоминания 1 q2 - состояние, когда нет единицы для запоминания q2 0-> q2 0l q2 1-> q2 2l q2 2-> q2 4l q2 3-> q2 6l q2 4-> q2 8l 3. если цифры от 5 до 9, то нужно запомнить 1 и прибавить на следующем шаге q2 5-> q3 0l q2 6-> q3 2l q2 7-> q3 4l q2 8-> q3 6l q2 9-> q3 8l q3-состояние, когда мы умножаем на 2 и прибавляем 1 к результату 3. если цифры от 0 до 4, то после "избавления" от 1 ничего запоминать не нужно q3 0-> q2 1l q3 1-> q2 3l q3 2-> q2 5l q3 3-> q2 7l q3 4-> q2 9l 4. если цифры от 5 до 9, то после "избавления" от 1, мы снова ее запоминаем q3 5-> q3 1l q3 6-> q3 3l q3 7-> q3 5l q3 8-> q3 7l q3 9-> q3 9l 5. заканчиваем программу, когда встречаем пустой символ q2 p-> q0 n q3 p-> q0 1n если мы все еще помним 1, а уже число закончилось, то на пустой клетке пишем 1.

Ответ в прикрепленной картинке