Какой тип автомата Google Turing Doodle?

В честь дня рождения Алана Тьюринга Google опубликовал рисунок, показывающий машину. Что за машина это каракули? Может ли он выражать язык Тьюринга?

Существуют очевидные отличия от классической машины Тьюринга: конечная лента, ограничения на то, как можно связать состояние, ...

Каракули еще можно найти здесь

(Дисплей в правом верхнем углу показывает ожидаемый результат.)

Лента в середине разделена на квадраты, которые могут содержать пробел, ноль или единицу. Голова расположена над одним из квадратов и используется для чтения и письма.

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

После запуска машины загорается первое состояние справа от зеленой кнопки, затем следующее справа и т. Д. Каждое состояние содержит одну из следующих команд:

• пусто = ничего не делать (просто перейти в следующее состояние)
• 1 = записать единицу на ленту в текущей позиции головы
• 0 = записать ноль на ленту в текущей позиции головы
• стрелка влево = переместить голову на один шаг влево
• стрелка вправо = переместить голову на один шаг вправо
• условие: если значение под заголовком равно значению, указанному в квадрате, переходите ко второй строке состояний. если нет, переходите к следующему состоянию справа
• прыжок влево: возврат к (фиксированному) предыдущему состоянию, но только в верхнем ряду [я изначально забыл это, спасибо @Marzio!]

Нет возможности «перекрыть» два прыжка (один над другим). Машина останавливается, когда она покидает состояние, и справа от нее нет следующего состояния.

(После остановки устройства содержимое ленты сравнивается с содержимым дисплея, но я не считаю, что это является частью предполагаемой функциональности устройства.)

При условии, что:

• мы можем добавить произвольно большое количество строк («строк состояния»)
• строки могут быть сколь угодно длинными
• лента бесконечна

Я попытался создать конфигурацию машины Doodle Алана Тьюринга, которая имитирует машину описанную в « Маленьких машинах Тьюринга и обобщенном соревновании за занятым бобром », которая имеет проблему остановки, которая зависит от открытой (насколько мне известно) проблемы, подобной Collatz. Полная картина доступна здесь .$M_4$

... так что даже если Doodle AT, возможно, не завершен по Тьюрингу (из-за неперекрывающегося оператора перехода влево только в первом ряду), он достаточно мощный, чтобы пройти тонкую грань (не) разрешимости: - D

РЕДАКТИРОВАТЬ: TURING Doodle TURING завершена

(Я оставляю предыдущий ответ выше, потому что я не уверен, что эта часть верна :-)

Я думаю, что даже с одним левым неперекрывающимся прыжком, Тьюринг-дудл завершен! , (Простая) идея состоит в том, чтобы использовать саму ленту для хранения текущего состояния и использовать несколько ячеек для представления большего алфавита.

Например, 2 состояния 8 символов TM могут быть смоделированы с использованием следующего представления ленты:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

Каракули Тьюринга могут:

1. $s$
2. $b2, b1, b0$
3. напишите следующий символ, переместите голову в «макросоту» слева или справа и сохраните в ней следующее состояние; на рисунке ниже эти операции (которые могут быть выполнены для последовательности ячеек с использованием действий перемещения влево / вправо и записи) называются «MW»;
4. наконец, перенесите элемент управления в верхний ряд, который одним прыжком влево вернет элемент управления к шагу 1.

Полная картина доступна здесь .

$TM$$DM$

Машина снабжена «лентой» (аналогом бумаги), проходящей через нее, и разделена на секции (называемые «квадратами»), каждая из которых может иметь «символ». В любой момент есть только один квадрат, скажем r-й, с символом S (r), который находится «в машине». Мы можем назвать этот квадрат «отсканированным квадратом». Символ на отсканированном квадрате можно назвать «отсканированным символом». «Отсканированный символ» является единственным, о котором машина, так сказать, «непосредственно осведомлена». Однако, изменяя свою m-конфигурацию, машина может эффективно запоминать некоторые символы, которые она «видела» (сканировала) ранее. Возможное поведение машины в любой момент определяется m-конфигурацией qn и сканированным символом S (r). Эта пара qn, ​​S (r) будет называться «конфигурацией»: таким образом, конфигурация определяет возможное поведение машины. В некоторых конфигурациях, в которых отсканированный квадрат не заполнен (т. Е. Не имеет символа), машина записывает новый символ в отсканированный квадрат: в других конфигурациях стирает отсканированный символ. Машина также может изменить сканируемый квадрат, но только сместив его на одно место вправо или влево. В дополнение к любой из этих операций m-конфигурация может быть изменена. Некоторые из записанных символов {232} образуют последовательность цифр, которая является десятичной дробью вычисляемого действительного числа. Другие просто грубые заметки, чтобы «помочь памяти». Только эти грубые заметки будут стерты. не имеет символа) аппарат записывает новый символ на отсканированном квадрате: в других конфигурациях он стирает отсканированный символ. Машина также может изменить сканируемый квадрат, но только сместив его на одно место вправо или влево. В дополнение к любой из этих операций m-конфигурация может быть изменена. Некоторые из записанных символов {232} образуют последовательность цифр, которая является десятичной дробью вычисляемого действительного числа. Другие просто грубые заметки, чтобы «помочь памяти». Только эти грубые заметки будут стерты. не имеет символа) аппарат записывает новый символ на отсканированном квадрате: в других конфигурациях он стирает отсканированный символ. Машина также может изменить сканируемый квадрат, но только сместив его на одно место вправо или влево. В дополнение к любой из этих операций m-конфигурация может быть изменена. Некоторые из записанных символов {232} образуют последовательность цифр, которая является десятичной дробью вычисляемого действительного числа. Другие просто грубые заметки, чтобы «помочь памяти». Только эти грубые заметки будут стерты. Некоторые из записанных символов {232} образуют последовательность цифр, которая является десятичной дробью вычисляемого действительного числа. Другие просто грубые заметки, чтобы «помочь памяти». Только эти грубые заметки будут стерты. Некоторые из записанных символов {232} образуют последовательность цифр, которая является десятичной дробью вычисляемого действительного числа. Другие просто грубые заметки, чтобы «помочь памяти». Только эти грубые заметки будут стерты.

Я утверждаю, что эти операции включают в себя все те, которые используются при вычислении числа. Защита этого утверждения будет легче, когда теория машин знакома читателю. Поэтому в следующем разделе я приступаю к развитию теории и предполагаю, что понимается, что подразумевается под «машиной», «лентой», «сканированием» и т. Д.

Это отрывок из оригинальной статьи Тьюринга «О вычислимых числах с приложением к проблеме Entscheidungs».

Современным хорошим компаньоном к статье, которую я рекомендую, является «Аннотированная Тьюринг » Чарльза Петцольда.

Как вы можете видеть, Google только что попытался напомнить машину, которая очень похожа на описание Тьюринга.

РЕДАКТИРОВАТЬ: Предполагая, что полный алфавит ТМ от Google показан в конце игры после нажатия на иконку кролика , и учитывая тот факт, что он генерирует бесконечную последовательность, получил больше строк и столбцов (поэтому мы можем предположить, что мы можем добавить любой ), имеет прыжки влево (а также перекрывающиеся прыжки влево) в любом ряду , имеет условный и безусловный переход между соседними рядами, я думаю, что Тьюринг завершен .

В головоломках прыжки разрешены на обеих линиях, но они не могут перекрываться. На заключительном дудле последовательности кроликов в конце игры они разрешают переходы на каждой строке, и их можно заключить в скобки, поэтому [()] разрешено, но ([)], по-видимому, недопустимо.

Я буду использовать следующие предположения:

1. $0$$1$$\epsilon$
2. Машина может использовать любое фиксированное количество линий
3. Прыжки влево разрешены на любой строке (я буду использовать один левый прыжок на строку)
4. $\epsilon$$0$$1$

С этими допущениями машина Google Doodle завершена .

$0$$1$$\epsilon$$0$$1$$n$ е состояния является назначенным государством останова.

$3(n - 1) + 1$$5n + 1$

$\epsilon$$0$$1$$\epsilon$$0$$1$$0$$1$

GDM моделирует TM следующим образом:

1. $1$ .
2. $j$
3. $\epsilon$$0$$1$ с). Не будет никаких препятствий из-за дизайна.
4. $\epsilon$ -Write ранее) и имитирует движение ТМА (влево, вправо, или ничего)
5. $0$$1$ ).
6. $0$$1$ в каждом состоянии предыдущего шага, он должен переноситься восходящим способом.

Выберите свою любимую универсальную ТМ и внедрите ее в описанную выше процедуру, чтобы получить универсальный GDM.