Синтез программ, разрешимость и проблема остановки

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

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

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

Существует TM, который решает проблему остановки для подмножества машин Тьюринга; и $S$
Все разрешимые проблемы решаются хотя бы одной машиной Тьюринга в ? $S$

Конечно, поиск машины Тьюринга в не может быть вычислимым сам по себе; но мы игнорируем эту проблему. $S$

РЕДАКТИРОВАТЬ: Основываясь на ответе Шоулла ниже, кажется, что (а) эта идея слишком плохо определена, чтобы быть осмысленной, или (б) моя предыдущая попытка была не совсем подходящей. Как я пытаюсь уточнить в комментариях к ответу Shaull, моя цель не в том , что мы гарантировать , что вход TM в . Что я действительно имел в виду под моим вопросом, может ли существовать такой , что членство в является разрешимой проблемой . Программа для решения проблемы остановки для , предположительно, записывает «неверный ввод» на ленте или что-то в этом роде, если ему дан вход, который он распознает как отсутствующий в $S$ $S$ $S$ $S$ $S$ , Когда я формулирую это так, я не уверен, позволяет ли это нам решить проблему остановки или нет, или применима ли теорема Райса (является ли разрешимость семантическим свойством языка относительно теоремы Райса?)

turing-machines undecidability halting-problem Patrick87
источник

думаю, что есть законный / существенный вопрос на границах теории, скрывающейся где-то здесь, но не в текущей форме, тем не менее, +1 за попытку [и этот отказ от ответственности в начале удивляет, учитывая ваш статус представителя / модератора] ... возможно, это вопрос , который вы читали? алгоритм решения turings останавливая проблемы

ВЗН

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

S_{n}

$S_n$

S_{n}

$S_n$

vzn

Я думаю, что может быть проблема с постановкой проблемы.

Рассмотрим множество является решающим элементом своего языка . Проблема остановки решаема для этого набора (то есть, если нам обещают, что вход находится в этом наборе). На самом деле, это тривиально (машины в всегда останавливаются). $S=\{M: M$ $\}$ $S$

Кроме того , очевидно , каждый разрешима язык в . $S$

EDIT: на основе изменений в вопросе - действительно, членство в будет неразрешимым: если содержит машину для каждого разрешимого языка, то . Таким образом, по теореме Райса, если разрешима , то содержит каждую машину, но тогда проблема остановки неразрешима на . $S$ $S$ $S\neq \emptyset$ $S$ $S$ $S$

Shaull
источник

S = {⟨ A ⟩ ∣ \forall x . A (x) ↓, L (A) \in R}

$S = \{\langle A \rangle \mid \forall x. A(x) \downarrow, L(A) \in \mathrm{R}\}$

L (A) \in R

$L(A)\in R$

A

$A$

Ах, верно. Фиксированный комментарий.

Рафаэль

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

Patrick87

(ps Извините, что неправильно указал ваше имя в моих изменениях. Мне слишком рано делать CS.SE, и это становится все более вероятным)

Patrick87

Синтез программ, разрешимость и проблема остановки

Ответы: