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