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

31

Я знаю, что проблема остановки вообще неразрешима, но есть некоторые машины Тьюринга, которые явно останавливаются, и некоторые, которые явно не делают. Из всех возможных машин Тьюринга самая маленькая, где никто не может доказать, останавливается она или нет?

halting-problem Аарон
источник

10

Ответ зависит от специфики модели машины (количество символов и т. Д.). Согласно статье в Википедии о Busy Beaver, есть двухсимвольная 5-ми точная машина, которая не знает, останавливается она или нет.

Каве

1

Обратите внимание, что вопрос Аарона не о разрешимости данного языка, а о существовании доказательства того, что конкретная машина Тьюринга останавливается. Для любой машины Тьюринга «ее» проблема остановки (независимо от того, останавливается ли эта машина на пустом входе) является «разрешимой»: это либо Да, либо Нет, и оба языка {Да} и {Нет} разрешимы. Это очень отличается от того, есть ли у человека доказательство того, что машина останавливается или нет. Аарон, если ты имеешь в виду «какой самый маленький такой, что язык останавливается на неразрешимым», можешь ли ты отредактировать свой вопрос?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

Микаэль Кадилхак

1

@ MichaëlCadilhac Проблема остановки обычно интерпретируется как "При наличии машины и ввода останавливается ли для ввода ?" не «Учитывая машин , делает привал для всех входов?»

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

Дэвид Ричерби

@DavidRicherby: Для меня проблема остановки - это язык машин (кодов), которые останавливаются на пустом вводе. Если это не подразумеваемое значение здесь, я думаю, что это должно быть определено, чтобы рассеять возможную (хорошо, моя) путаница.

Микаэль Кадилхак

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

ВЗН

38

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

$TM(2,3), TM(2,2), TM(3,2)$ (где - множество машин Тьюринга с состояниями и символами). $TM(k,l)$ $k$ $l$

Разрешимость и находится на границе, и ее трудно установить, поскольку она зависит от гипотезы Коллатца, которая является открытой проблемой. $TM(2,4)$ $TM(3,3)$

См. Также мой ответ на cstheory о коллатцоподобных машинах Тьюринга и « Маленьких машинах Тьюринга и обобщенном соревновании занятых бобров » П. Мишеля (2004) (в котором предполагается, что также разрешима). $TM(4,2)$

Комментарий Каве и ответ Мухаммеда верны, поэтому для формального определения стандартных / нестандартных машин Тьюринга, используемых в такого рода результатах, см. Работы Turlough Neary и Дэмиена Вудса на небольших универсальных машинах Тьюринга, например, сложность небольших универсальных машин Тьюринга: опрос (правило 110 ТМ слабо универсально).

Марцио де Биаси
источник

2

Разве проблема остановки для любого заданного конечного набора машин Тьюринга не всегда разрешима? Так как в есть только конечное число машин , должна быть возможность создать справочную таблицу, которая правильно говорит, какие машины останавливаются, а какие нет, и поэтому должна быть машина Тьюринга, которая использует эту справочную таблицу. правильно ответить на вопрос.

T M (4, 2)

$TM(4, 2)$

Таннер Светт

2

@TannerSwett: здесь мы рассматриваем набор остановки или, другими словами, для которых машины Тьюринга разрешима (см. статью Мишеля).

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$

Марцио Де Биаси

32

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

Например, возьмем машину Тьюринга, которая ищет доказательство противоречия в ZFC. Тогда, если ZFC непротиворечив, он не остановится, но вы не можете доказать это в ZFC (из-за второй теоремы Гёделя о неполноте).

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

Денис
источник

ZFC? Что означает ZFC? Я просто не могу понять это из контекста.

Акапулько

7

@Acapulco lmgtfy.com/?q=zfc&l=1

Сашо Николов

Смешно! хорошо. Я получил lmgtfy'ed. Touche. Не думал, что это будут инициалы, которые бы сразу и однозначно относились к этой теме. В любом случае я не думаю, что было бы больно добавлять вежливое уточнение «ZFC (теория множеств Цермело – Френкеля)» при первом упоминании, также чтобы избежать двусмысленности в случае, если есть? :)

Акапулько

16

@Acapulco, пожалуйста, смотрите тур и справочный центр . Любой теоретик-компьютерщик знал бы, что означает ZFC, поэтому нет необходимости в разъяснениях.

Каве

1

В частности, обратите внимание на недавно обнаруженные символьные машины с ZFC-независимой проблемой остановки, обсуждаемые здесь (7918 состояний), здесь и здесь (1919 состояний). Количество штатов почти наверняка будет уменьшаться в дальнейшем.

2

$2$

Res

5

Ни у кого нет доказательств того, останавливается ли универсальная машина Тьюринга или нет. На самом деле такое доказательство невозможно из-за неразрешимости проблемы Остановки. Самым маленьким является универсальная машина Тьюринга с двумя символами и двумя состояниями, найденная Алексом Смитом, за которую он выиграл приз в 25 000 долларов.

Мухаммед Аль-Туркистани
источник

4

Однако обратите внимание, что, согласно цитируемой странице Википедии, доказательство универсальности оспаривается. Кроме того, это не стандартная модель машин Тьюринга: предположительно универсальная машина не имеет состояния остановки, поэтому не может имитировать любую машину, которая останавливается, по крайней мере, в стандартном смысле того, что делает универсальная машина Тьюринга.

Дэвид Ричерби

2

@DavidRicherby: Я думаю , что слабо -универсальность правилу 110 вполне принято: он требует двух разных слов повторяются на левой и правой части ввода, и Остановки условием является создание специального планера (порождена тогда и только тогда , когда смоделированная машина останавливается). См. Мэтью Кука "Универсальность в элементарных клеточных автоматах".

Марцио Де Биаси

-4

неточно сформулированный, но разумный общий вопрос, который можно изучить несколькими конкретными техническими способами. Есть много «маленьких» машин, измеряемых состояниями / символами, где остановка неизвестна, но «наименьшая» машина невозможна, если не будет предложена какая-либо оправданная / количественная метрика сложности ТМ, которая учитывает как состояния, так и символы (очевидно, пока никто не предложил).

$x \times y$ $x$ $y$

$x,y$

ВЗН
источник

2

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

Дэвид Ричерби

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

vzn

1

2 \leq i \leq 4

$2\leq i\leq 4$

k_{i}

$k_i$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

Дэвид Ричерби

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

ВЗН

x

$x$

y

$y$

x

$x$

y

$y$

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

Ответы: