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

31

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

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

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

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

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

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

AlexC
источник
3
Кстати, я не могу сказать, будут ли вопросы о машине Тьюринга лучше публиковаться здесь или на MathOverflow. Сначала я пытаюсь здесь, потому что у cs есть тег "машины тьюринга", а у MO нет. Я не кросс-постинг в соответствии с политикой, но я рад, что этот вопрос будет перенесен, если это будет лучшим местом для него.
AlexC
12
Я думаю, что это разумное место для этого вопроса.
Суреш Венкат
4
Добавлен «универсальный» в заголовок. (Простейшая машина Тьюринга с двумя состояниями останавливается из любого состояния при чтении любого символа.)
Джефф
1
ps yrs ago искал исследование по универсальности тюринга в клеточных автоматах, но безрезультатно. Похоже, что в литературу не вошло много. эта концепция довольно широко распространена в «фольклоре», но не очень основана на формальных аргументах / доказательствах / теории. Вольфрам много сделал в этой области, но, как многие отмечали, большая часть его стиля более экспериментаторская.
vzn
2
Хех. Сотрудник помещает бумагу ( arxiv.org/abs/1904.09828 ) в Slack и бормочет меня, я гуглю "2,18 универсальный токарный станок", и вот мы здесь. Поздравляем!
Голубой

Ответы:

12

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

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

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

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

Neary, Woods SOFSEM 2012, самые маленькие известные универсальные машины Тьюринга

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

Найл Мерфи
источник
13

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

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

картина из бумаги

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

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

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

Марцио де Биаси
источник
1
Ссылка идет на статью Алекса Смита, а не на статью, которую, я думаю, вы намеревались.
Джефф
Очень полезная ссылка. Спасибо. Похоже, мне лучше всего выбрать (2, 18) машины.
AlexC
В этой статье говорится, что машины Тьюринга с 2 символами состояния 3 имеют решаемую проблему остановки, поэтому машина Тьюринга с символом 3 состояния Вольфрама 2 не может быть универсальной.
Крейг Файнштейн,
1
@CraigFeinstein: ТМ Wolfram (2,3) немного отличается от обычных ТМ: он не имеет состояния остановки и требует бесконечной неповторяющейся поддержки ленты. Его даже нельзя считать слабо универсальным (слабо универсальный ТМ требует бесконечного повторения в обоих направлениях)
Марцио Де
11

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

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

Дэвид Эппштейн
источник
Ограничение на 2 состояния будет гораздо проще имитировать, чем ТМ с большим количеством состояний. В настоящий момент я думаю, что мне будет проще создать двухцветную 18-цветную ТМ, чем трехстороннюю и даже небольшое количество цветов.
AlexC
(2, 5) интересно, и может быть полезным промежуточным этапом для меня. Но, судя по этим ссылкам, мне нужно перейти к (2, 18), чтобы найти такую, которая позволит мне начать с конечного числа чёрных ячеек на исходной ленте. Благодарность!
AlexC
5

S0s<SС0с<С2LрС+4SС

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

(с,s)Lр(сновый,sновый,испускают)L .

сLс(с,0,L,Получать)р

сс(с,s,испускают)(с,0,L,Получать)сс
ss0L метка : до тех пор, пока состояние соответствует этому, продолжайте цикл уменьшения / приращения, но если это не так, мы закончим, и мы очистим.

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

  1. с(с,0,dяр,Получать)dяр

  2. (с,s)(сновый,sновый,испускают)

  3. (с,s,испускают)(с,s-1,испускают)s>0

  4. (с,0,испускают)с

  5. (с,s,dяр,Получать)(с,s+1,dяр,Получать)dяр

  6. (с,s,dяр,Получать)(с,s)dяр

С+3SС

Бруно Ле Флох
источник
0

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

ВЗН
источник
-3

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

user2230103
источник
Пытаясь разобраться с этим длинным аргументом, я делаю вывод, что (2,3) -ТМ Смита явно универсальна только в слабом смысле. Тем не менее, некоторые другие ответы уже обсуждали это подробно, со ссылками на статьи с классификациями, которые пытаются сделать этот рассказ математически точным. Также обратите внимание, что не все модели ТМ предполагают бесконечную пустую ленту для начала.
Андрас Саламон
Ваш комментарий только показывает, что вы игнорируете область. Я не использовал никаких сложных понятий для кого-то, кто разбирается в основах машин Тьюринга (например, начальная конфигурация, пустой символ и т. Д.). Опять же, единственное различие, и уже принятое для других видов автоматов, состоит в том, что машина Смита-Вольфрама Тьюринга не запускается с чистого листа. Правильный ответ -3 ясно показывает, что демократия и популярность не означают правду, а более актуальная реализация, чем что-либо еще, учитывая вид клоунов, которые сейчас правят миром под эгидой демократии.
user2230103