Алгоритм машины Тьюринга для подсчета 0 и записи количества в двоичном

Question

Мне нужен алгоритм для машины Тьюринга, который читает строку 0, а затем записывает на ленту, сколько их было в двоичном виде.

Я понимаю, что на практике машина фактически не будет считаться0, но я довольно озадачен тем, как это сделать.

Я предпочитаю сначала указать место, где двоичное число начинается с X или чего-то еще, а затем просто написать 1 для первых 0 и для каждого из следующих 0, если младший бит0 это становится 1, но что если это 1?Может быть, превратить его в 0 и продолжать влево, переставляя все 1 в 0, пока я не найду 0 или пробел, чтобы превратить в 1?Опять же, в этом случае это одно и то же, независимо от LSB, потому что я буду делать то же самое, только 0 будет первой позицией ...

Хмм ... резиновая уточка ...

Answer 1

Предположим, входная лента - #00000000000#, где начальная позиция чтения - первая 0.

1. Двигайтесь вправо до достижения конца #, поддерживая четность числа встреченных 0 (сначала 0, затем 1, затем 0, ...) Замените первые 0 каждой пары на -. Чтение - игнорируется и не изменяет четность.

2. Запись четности на выходную ленту и перемещение влево (для записи битов по порядку)

3. Верните входную головку влево # и перейдите к 1.

В конце первого прохода входная лента будет #-0-0-0-0-0-#, а вывод - 1.

В конце второго прохода: #---0---0---# и 11.

В конце третьего прохода: #-------0---# и 011.

В конце четвертого прохода: #-----------# и 1011.

Answer 2

Проверьте этот симулятор машины Тьюринга и его пример программы двоичного подсчета:

Машина Uber Turing позволяет вам запрограммировать машину Тьюринга - универсальное теоретическое устройство, которое может адаптироваться для симуляции логики любого компьютерный алгоритм. С помощью это программное обеспечение, которое вы можете создать новые алгоритмы, а также редактирование уже подготовлен кем-то через открытие и изменение их через удобная визуальная IDE.

Answer 3

Редактировать: Я уступаю Бейнвиллю.

Я понял, что хочу сделать прошлой ночью, и мне потребовались две отдельные машины Тьюринга, и это, вероятно, обман.

Голова первой машины будет проходить через ленту ввода и просто запустит вторую машину, если она отсканирует 0.

Вторая машина будет просто машиной добавления и добавит 1 к текущему номеру, что довольно легко сделать, это просто длинное сложение, и вы можете создать состояние, которое говорит, что есть остаток, и продолжать движение влево, пока достичь нуля (и заменить его на 1) или найти пустое место (и создать 1).

Бейнвилл выигрывает мой голос.