С двумя лентами или ленточным алфавитом (отличающимся от входного алфавита) больше, чем просто {1, пусто}, можно добиться гораздо большего.Фактически, единственная вещь, для которой вам нужна вторая лента или расширенный алфавит, - это пометка, где находятся начало и конец ввода.
Итак, мы можем начать следующим образом: перебрать ввод, стирая все остальные 1.Одновременно мы можем посчитать соотношение длины ввода.Это может быть сделано только с двумя состояниями, назовите их ДАЖЕ и ODD.Начните в ДАЖЕ состоянии.Когда вы читаете 1, переключитесь в состояние ODD.В состоянии ODD, когда вы читаете 1, сотрите его и переключитесь в состояние EVEN.
Затем вернитесь к тому же, используя еще два состояния.Затем перейдите к вводу в третий раз с еще двумя состояниями.На этом этапе либо ваша машина отклонила, когда один из циклов считал нечетное число 1, либо у вас теперь есть 1/8 числа, равного 1.
Используя аналогичную конструкцию, вы можете запустить вводстирая 4 из каждых 5 1 и убедившись, что длина ввода кратна 5. Это можно сделать с 5 состояниями.Сделайте это дважды.
Теперь, если все проверки на четность и (5-арность) пройдены и у вас остался один 1, то ваш исходный ввод имел 1 * 5 * 5 * 2 * 2 * 2 =200 1 в этом.В противном случае нет.Общее количество использованных состояний: 2 + 2 + 2 + 5 + 5 = 16 (или 18, если вы посчитаете свои состояния принятия и отклонения).
Более сложные конструкции могут выполнять ту же задачу в меньшем количестве состояний, но вы в значительной степениГарантируется, что время выполнения будет нелепым, и вам понадобится ленточный алфавит не менее {0,1, пусто}.Если вы действительно хотите получить представление о том, как работают машины Тьюринга, подумайте о том, как алгоритм компенсирует недостаток оперативной памяти у машины Тьюринга (в форме состояний).Не могли бы вы сделать аналогичный алгоритм для языка {1 ^ 99}?Как насчет {1 ^ 97} (подсказка: это может быть сделано менее чем с 97 состояниями, но вам понадобится немного нового умного)?