Алгоритм деления пополам для произвольной булевой функции

[involume]

То есть это будет выглядеть вот так? $10\lambda01\lambda11\lambda00$ И что нам это даст? Мы делаем шаг на одной ленте. Копируем этот символ на другую ленту, далее делаем ещё шаг вперёд, записываем опять это значение на другую ленту. Далее на первой ленте пишем $\lambda$. На второй получается мы тоже это должны сделать. Я правильно понимаю?

[nikvic]

Вы так и не ответили, каковы требования к машине. Что является начальным состоянием, как должно выглядеть конечное.

[involume]

На начальном состоянии у нас есть одна лента, на конечном мы должны получить ленту, которая будет разделена на две. Я выше привёл предположение в состояниях, как мы бы получили две ленты, но кажется что она не правильное.

[nikvic]

Тогда причём здесь вторая лента?
Деление пополам на одной ленте легко устроить, имея пару лишних букв. Пишем их в начала, а потом двигаем направо по очереди, одну - на один символ, вторую - на два.
Придётся побегать