Как формально описать этот алгоритм для машины Тьюринга?

Question

Уоринг: Эту задачу дал мой профессор, которому 80 лет, и никто не понимает, чего он иногда хочет, я не ожидаю более менее стандартного подхода к этой проблеме, не только потому, что проблема трудная, но и потому, что мой профессор стар Школа экс-сумасшедшего экс-парня;) (он любит делать сложные вещи, просто чтобы объяснить, почему это опубликовано здесь)

Эта задача чисто теоретическая, но я не знаю, как ее формализовать словами.

На входе дается 9-битный двоичный код, мы должны вывести "0" на выходе, если количество битов со значением "1" в два раза меньше количества битов со значением "0", если это условие ложно, что мы должны выведите "1" на выходе.

В моем описании я предложил ввести счетчик, а затем подсчитать биты, имеющие значение 1, а затем сделать вывод на основе этого счетчика, но я был объявлен идиотом, и мне сказали, что есть путь без счетчика и Я выбираю самый сложный путь. Кто-нибудь знает лучший способ определить, что выводить?

Спасибо заранее, и извините, если описание выглядит грязно

Answer 1

Когда TM считывает входные биты, номер состояния должен захватывать количество увиденных битов, от 0 до 9, чтобы мы могли распознать, когда мы дойдем до конца, и количество увиденных 1 бит, причем соответствующие случаи являются 0, 1, 2, 3 и>=4.

Для кодирования всех соответствующих возможностей требуется менее 10*5=50 состояний. Когда машина входит в одно из состояний, указывающих, что 9 входных битов были замечены, она записывает 0, если это указывает, что 3 1 были замечены, или 1 в противном случае, затем останавливается.

Обратите внимание, что нам не нужно было использовать ленту для хранения - язык ввода является обычным, поэтому его можно выбрать с помощью конечного автомата, а неограниченное хранение не требуется.

Answer 2

Хотя Мэтт прав, вы можете обобщить эту проблему для произвольных входных размеров, используя хранилище.

1. Перейти к началу ленты
2. Двигаться вперед в поисках без опознавательных знаков 1, Отметьте это.
   • Если вы не можете найти без опознавательных знаков 1перейдите к шагу 7.
3. Вернуться к началу ленты
4. Ищите без опознавательных знаков 0, Отметьте это.
   • Если вы не можете найти без опознавательных знаков 0, перейдите к шагу 9.
5. Ищите другой без опознавательных знаков 0, Отметьте это.
   • Если вы не можете найти без опознавательных знаков 0, перейдите к шагу 9.
6. Перейти к шагу 1
7. Перейти к началу вашего ввода.
8. Ищите без опознавательных знаков 0,
   • Если вы не нашли его, выведите 0, Halt.
9. Выход 1, Halt.

Это будет работать для любого размера ввода. Интуитивно мы ищем 2 0для каждого 1 на входе, убедившись, что их вдвое больше 0 биты как 1 биты.