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

Question

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

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

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

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

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

Answer 1

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

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 бит.

Answer 2

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

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

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