Какая простейшая универсальная машина Тьюринга с двумя состояниями?

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

До сих пор я создал игровое состояние, которое кодирует машину Тьюринга с 2 состояниями и 3 символами Алекса Смита . Тем не менее, кажется (по общему признанию, основанному на Википедии), существует некоторое противоречие относительно того, является ли машина (2, 3) действительно универсальной.

Ради Ригора, я бы хотел, чтобы мое доказательство содержало "неоспоримый" UTM. Итак, мои вопросы:

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

2. Если (2,3) машина широко не принята в качестве универсальных, что наименьшее N такой, что (2, N) машина noncontroversially принята в качестве универсальной?

Отредактировано, чтобы добавить: Было бы также полезно знать любые требования к бесконечной ленте для упомянутых машин, если вы случайно их знаете. Кажется, что (2,3) машина требует начального состояния ленты, которое непериодично, что будет немного трудно симулировать в рамках правил карточной игры.

Со времени работы, процитированной в предыдущих ответах, появились новые результаты. Этот обзор описывает современное состояние (см. Рисунок 1). Размер самой маленькой из известных универсальных машин Тьюринга зависит от деталей модели, и вот два результата, которые имеют отношение к этому обсуждению:

• Существует стандартная универсальная машина из 18 символов с 2 состояниями (Рогожин, 1996. TCS, 168 (2): 215–240). Здесь мы имеем обычное понятие пустого символа в одном или обоих направлениях одной ленты.
• Существует слабо универсальная машина с двумя состояниями и четырьмя символами (Neary, Woods 2009. FCT. Springer LNCS 5699: 262-273). Здесь у нас есть одна лента, содержащая конечный ввод и постоянное (не зависящее от входного) слово повторяемое бесконечно вправо, с другим постоянным словом l, повторяемое бесконечно налево. Это улучшает слабо универсальную машину, упомянутую Дэвидом Эппштейном.$r$$l$

Похоже, что (2,18) является наиболее полезным для вас.

Обратите внимание, что теперь известно, что все самые маленькие универсальные машины Тьюринга работают за полиномиальное время. Это подразумевает, что их задача прогнозирования (учитывая, что машина , ввод w и ограничение по времени t в унарном виде, принимает ли M в течение времени t ?), Является P-полной. Если вы пытаетесь сделать игру (для одного игрока), это может быть полезно, например, чтобы показать, что NP-сложно найти начальную конфигурацию (комбинация карт), которая приведет к победе в течение t ходов. Для решения этих сложных проблем мы заботимся только о конечной части ленты, что делает (чрезвычайно маленькие) слабо универсальные машины очень полезными.$M$$w$$t$$M$$w$$t$

На рисунке показаны самые маленькие из известных универсальных машин для различных моделей машин Тьюринга (взяты из Neary, Woods SOFSEM 2012), ссылки можно найти здесь .

Это не настоящий ответ на ваш вопрос (я не знаю много о (2,3) машинных дебатах); но я предлагаю вам газету " Маленькие машины Тьюринга и общее соревнование занятых бобров ". Я быстро прочитал это некоторое время назад, и у него есть хороший график с границами между 4 типами маленьких ТМ:

• разрешима
• открытая коллатцоподобная проблема
• $3x + 1$
• универсальный

(возможно, некоторые результаты были улучшены).

Понятие ТМ, используемое в статье, является стандартным определением ТМ, используемым в работах на небольших универсальных машинах Тьюринга:

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

Также возможно достичь универсальности с 7 состояниями и 2 символами, хотя применимы многие из тех же самых возражений (неоднородные начальные условия на бесконечной ленте и необычные условия завершения). См. Http://11011110.livejournal.com/104656.html и http://www.complex-systems.com/abstracts/v15_i01_a01.html.

Они основаны на моделировании сотового автомата Правила 110, доказанного универсальным Мэтью Куком, и Кук также нашел симуляцию по 5 символам из 2 состояний Правила 110, если вы ограничены только двумя состояниями.

$S$$0\leq s < S$$C$$0\leq c< C$$2$$\text{L}$$\text{R}$$C+4SC$

В любом случае, только текущая ячейка или две ячейки, участвующие в переходе, могут иметь улучшенные цвета: все остальные ячейки имеют свой истинный цвет. Мы хотим, чтобы наша машина вела себя следующим образом: проверила, какой истинный переход выполнить, переместила информацию об «истинном состоянии» из ячейки, которую мы хотим оставить, в целевую ячейку (это включает в себя много возвратов), очистила Клетку мы оставили (придав ей истинный цвет), повторите.

$(c,s)$$\text{L}$$\text{R}$$(c_{\text{new}}, s_{\text{new}}, \text{emit})$$\text{L}$ .

$c$$\text{L}$$c$$(c,0, \text{L},\text{receive})$$\text{R}$

Вот переходы для реализации этого. Почти во всех случаях двигайтесь в направлении, указанном текущим состоянием, затем переворачивайте состояние

1. $c \to (c,0,\langle dir\rangle,\text{receive})$$\langle dir\rangle$

2. $(c,s) \to (c_{\text{new}},s_{\text{new}},\text{emit})$

3. $(c,s,\text{emit}) \to (c,s-1,\text{emit})$$s>0$

4. $(c,0,\text{emit}) \to c$

5. $(c,s, \langle dir\rangle, \text{receive}) \to (c, s+1, \langle dir\rangle, \text{receive})$$\langle dir\rangle$

6. $(c,s, \langle dir\rangle, \text{receive}) \to (c,s)$$\langle dir\rangle$

$C+3SC$

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

Доказательство универсальности по Тьюрингу Алекса Смита для предположительно предложенной Вольфрамом машины Тьюринга с двумя состояниями и тремя символами определенно не вызывает сомнений. Данное доказательство универсальности (а не машины) требует бесконечного шаблона на ленте Тьюринга, и вопрос заключался в том, следует ли разрешать такие конфигурации (вы можете думать о обычно «пустой» ленте как о бесконечном повторяющемся шаблоне пустых символов). Был сделан вывод, что до тех пор, пока конфигурация на ленте машины является фиксированной (т.е. она не изменяется после начала ваших вычислений и остается неизменной для любых вычислений), универсальные вычисления выполняются машиной Тьюринга. Обратите внимание, что это НЕ противоречиво для правила 110 Элементарного клеточного автомата Вольфрама, доказавшего универсальность Вольфрама и Кука. Для доказательства универсальности правила 110 также требуется бесконечный шаблон исходной конфигурации, отличающийся с обеих сторон, и поэтому он имеет одинаковую природу для машины Тьюринга с двумя состояниями и тремя символами. Другая проблема заключалась в том, что, возможно, такое ослабление требования начального условия (незаполненного) сделало бы некоторые общепринятые универсальные автоматы без Тьюринга, такие как конечные автоматы, линейные ограниченные автоматы или автоматы с понижением частоты, чтобы упомянуть некоторые примеры, но это не так уважает хомскую иерархию. Поэтому, безусловно, не вызывает сомнений универсальность машины Тьюринга с двумя состояниями, состоящей из двух состояний, но для доказательства ее универсальности требовалось изменение того, что обычно считается котентами обычной ленты машины Тьюринга. Кстати, это не означает, что 2-состояние,