Частичное решение halting problem

[tenmin]

Пусть $H(P,D)$ частично решает проблему останова: $H(P,D)=1$ если $P(D)$ останавливается, $H(P,D)=0$ если $P(D)$ не останавливается и $H(P,D)=-1$ если дать однозначный ответ остановится $P(D)$ или нет - невозможно. "Невозможно" означает те случаи, когда иное значение $H(P,D)$, т.е. $1$ или $0$, приводит к логическому противоречию. Глядя на доказательство несуществования алгоритма решающего проблему останова, видим, что там приходят к противоречию вида $\exists P \exists D (H(P,D)=1 \Rightarrow P(D) \text{не ост.} \land H(P,D)=0 \Rightarrow P(D) \text{ост.})$. Значит должно выполняться следующее условие для $H$:

$$\forall P \forall D (H(P,D) =-1 \Leftrightarrow (H(P,D)=1 \Rightarrow P(D) \text{не ост.} \land H(P,D)=0 \Rightarrow P(D) \text{ост.}))$$

Короче, вопрос: существует ли такая $H$?

[patzer2097]

tenmin в сообщении #884803 писал(а):

"Невозможно" означает те случаи, когда иное значение $H(P,D)$, т.е. $1$ или $0$, приводит к логическому противоречию.

ага, то есть те случаи, когда $P(D)$ и остановится, и не остановится одновременно

[Munin]

tenmin в сообщении #884803 писал(а):

Короче, вопрос: существует ли такая $H$?

Существует. Например, выдающая всегда $-1.$

[tenmin]

Munin
Мне хотелось добиться абсолютно противоположного. Чтобы от $H$ была польза. Чтобы $H(P,D)$ для большинства $P$ и $D$ решало проблему останова. Чтобы $H(P,D)=-1$ только в случаях, когда иной ответ невозможен логически. Например, если $X(P)=N(H(P,P))$, где $N(1)$ не останавливается и $N(0)$ останавливается, то $H(X,X)=1 \Rightarrow X(X) \text{не ост.}$ и $H(X,X)=0 \Rightarrow X(X) \text{ост.}$. Надо чтобы только лишь в подобного рода случаях $H(P,D)=-1$.
Как определить этот третий случай, когда $H(P,D)=-1$, формально, чтобы от $H$ была польза и она была оптимальной?

-- 07.07.2014, 18:05 --

patzer2097
$1$ - остановится, $0$ - не остановится, $-1$ - не знаю и не могу знать.

[Munin]

Боюсь, сами попытки дать определение, когда эта функция должна и не должна выдавать $-1,$ будут логически противоречивы. Что-то похожее на парадокс брадобрея.

[patzer2097]

tenmin в сообщении #884946 писал(а):

$1$ - остановится, $0$ - не остановится, $-1$ - не знаю и не могу знать.

В этом случае происходит вот что. Если $P(D)$ останавливается, но Вы об этом "не знаете и не можете знать", то $H(P,D)$ равно одновременно и $+1$, и $-1$. Обратите внимание, что так не бывает

[Dan B-Yallay]

(Оффтоп)

patzer2097 в сообщении #884998 писал(а):

Если $P(D)$ останавливается, но Вы об этом "не знаете и не можете знать", то $H(P,D)$ равно одновременно и $+1$, и $-1$. Обратите внимание, что так не бывает

Шредингерский котёнок?

[arseniiv]

Если значения $H(P,D)$ определить аккуратно, без

tenmin в сообщении #884946 писал(а):

Чтобы $H(P,D)=-1$ только в случаях, когда иной ответ невозможен логически.

Потребовать ровно такое:

$$\begin{array}{l} H(P,D) = 1 \Rightarrow \operatorname{halts}(P(D)), \\ H(P,D) = 0 \Rightarrow \neg\operatorname{halts}(P(D)), \\ H(P,D) \in\{-1,0,1\},\end{array}$$

то можно вот что сказать:

tenmin в сообщении #884946 писал(а):

Как определить этот третий случай, когда $H(P,D)=-1$, формально, чтобы от $H$ была польза и она была оптимальной?

Не помню, но, вроде, можно определять всё лучшие и лучшие $H$, выдающие на месте $-1$ предыдущих $1$ или $0$. Разумеется, без избавления от счётного числа $-1$. Так что оптимальной нет. «Предела», разумеется, здесь никакого нет, потому что, тоже не помню, но длина всё более хороших $H$ должна расти.

Надо, чтобы кто-то подтвердил или опроверг.

-- Пн июл 07, 2014 22:54:08 --

arseniiv в сообщении #885023 писал(а):

«Предела», разумеется, здесь никакого нет, потому что, тоже не помню, но длина всё более хороших $H$ должна расти.

Не знаю, зачем я это в одно предложение засунул, т. к. второе не влечёт первое, это просто иллюстрация. Предела-то нет просто из доказательства, что такая $H$ без $-1$ не существует, конечно же.

[patzer2097]

arseniiv в сообщении #885023 писал(а):

Если значения $H(P,D)$ определить аккуратно <...> Потребовать ровно такое:

$$\begin{array}{l} H(P,D) = 1 \Rightarrow \operatorname{halts}(P(D)), \\ H(P,D) = 0 \Rightarrow \neg\operatorname{halts}(P(D)), \\ H(P,D) \in\{-1,0,1\},\end{array}$$

Это не является (однозначным) определением, потому что под него подпадет даже $H$, равная тождественно $-1$.

[Munin]

patzer2097
Вы невнимательно читаете, дальше arseniiv говорит о множестве $H(P,D),$ удовлетворяющих этим условиям.

[patzer2097]

Munin в сообщении #885064 писал(а):

patzer2097
Вы невнимательно читаете, дальше arseniiv говорит о множестве $H(P,D),$ удовлетворяющих этим условиям.

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

tenmin в сообщении #884946 писал(а):

от $H$ была польза и она была оптимальной

я не в силах

[tenmin]

arseniiv в сообщении #885023 писал(а):

Потребовать ровно такое:

$$\begin{array}{l} H(P,D) = 1 \Rightarrow \operatorname{halts}(P(D)), \\ H(P,D) = 0 \Rightarrow \neg\operatorname{halts}(P(D)), \\ H(P,D) \in\{-1,0,1\},\end{array}$$

Под такое определение подходит $H$, которая всегда $-1$ выдает, как Munin выше говорил.

arseniiv в сообщении #885023 писал(а):

Не помню, но, вроде, можно определять всё лучшие и лучшие $H$, выдающие на месте $-1$ предыдущих $1$ или $0$.

Да, это очевидно. Оптимальность я не в этом смысле имел в виду. Возьмем Ваше определение $H$. Оно задает целый класс таких $H$. Каждой $H$ соответствует множество пар $M=\{(P,D)\}$ для которых она решает проблему остановки, т.е. возвращает $1$ либо $0$, а для всех других пар не из этого множества она возвращает $-1$. Для некоторых $H$ это множество пар может быть пустым, т.е. $H$ все время возвращает $-1$. Для некоторых - конечным. Для еще каких-то - бесконечным. Допустим, что у $H$ это множество пар $M$ бесконечно. Будем считать $H$ оптимальной, если не существуют более короткой программы $H'$ с множеством пар $M':M\subset M'$.
Да, вот наверное так.

-- 07.07.2014, 22:57 --

Хотя нет, не то. Надо другое условие. По сложности $M$. Нужно $H$ c самым сложным $M$ (если оно есть). Надо определить, что значит "сложность $M$" и доказать, что есть верхняя граница.

-- 07.07.2014, 23:10 --

patzer2097 в сообщении #884998 писал(а):

В этом случае происходит вот что. Если $P(D)$ останавливается, но Вы об этом "не знаете и не можете знать", то $H(P,D)$ равно одновременно и $+1$, и $-1$.

Хорошо, еще раз. $1$ - остановится, могу доказать это, $0$ - не остановится, могу доказать это, $-1$ - не знаю остановится или нет потому, что не могу доказать ни то ни другое.

[patzer2097]

tenmin в сообщении #885088 писал(а):

Хорошо, еще раз. $1$ - остановится, могу доказать это, $0$ - не остановится, могу доказать это, $-1$ - не знаю остановится или нет потому, что не могу доказать ни то ни другое.

Ура! Наконец-то Вы сформулировали что-то более-менее понятное.
Я бы только так поправил Ваше условие: $H(P)=1$ если $P$ останавливается, $H(P)=0$ если $P$ не останавливается и это доказуемо, $H(P)=-1$ если $P$ не останавливается и это не доказуемо. Потому что обсуждать, что можете именно Вы (или еще кто-то) в рамках математической теории не получится.

tenmin в сообщении #884803 писал(а):

Короче, вопрос: существует ли такая $H$?

В любом случае, как она может не существовать - мы же ее задали тут? Уточните формулировку вопроса.

[Munin]

patzer2097
Вы забыли ещё один случай: когда $P$ останавливается, и это не доказуемо.

[patzer2097]

Munin в сообщении #885137 писал(а):

patzer2097
Вы забыли ещё один случай: когда $P$ останавливается, и это не доказуемо.

Такого случая нет: если $P$ останавливается, то это происходит за конечное число шагов алгоритма. Последовательное описание этих шагов и является доказательством того, что $P$ останавливается