2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Частичное решение halting problem
Сообщение07.07.2014, 06:17 
Пусть $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$?

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 11:42 
tenmin в сообщении #884803 писал(а):
"Невозможно" означает те случаи, когда иное значение $H(P,D)$, т.е. $1$ или $0$, приводит к логическому противоречию.
:twisted: ага, то есть те случаи, когда $P(D)$ и остановится, и не остановится одновременно :twisted:

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 11:47 
Аватара пользователя
tenmin в сообщении #884803 писал(а):
Короче, вопрос: существует ли такая $H$?

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

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 16:43 
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$ - не знаю и не могу знать.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 17:57 
Аватара пользователя
Боюсь, сами попытки дать определение, когда эта функция должна и не должна выдавать $-1,$ будут логически противоречивы. Что-то похожее на парадокс брадобрея.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 18:10 
tenmin в сообщении #884946 писал(а):
$1$ - остановится, $0$ - не остановится, $-1$ - не знаю и не могу знать.
В этом случае происходит вот что. Если $P(D)$ останавливается, но Вы об этом "не знаете и не можете знать", то $H(P,D)$ равно одновременно и $+1$, и $-1$. Обратите внимание, что так не бывает :twisted:

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 18:42 
Аватара пользователя

(Оффтоп)

patzer2097 в сообщении #884998 писал(а):
Если $P(D)$ останавливается, но Вы об этом "не знаете и не можете знать", то $H(P,D)$ равно одновременно и $+1$, и $-1$. Обратите внимание, что так не бывает
Шредингерский котёнок? :D

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 19:38 
Если значения $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$ не существует, конечно же.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 21:02 
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$.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 21:04 
Аватара пользователя
patzer2097
Вы невнимательно читаете, дальше arseniiv говорит о множестве $H(P,D),$ удовлетворяющих этим условиям.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 21:16 
Munin в сообщении #885064 писал(а):
patzer2097
Вы невнимательно читаете, дальше arseniiv говорит о множестве $H(P,D),$ удовлетворяющих этим условиям.
я читаю то, что написано :twisted:
а обсуждать всерьез проблемы типа
tenmin в сообщении #884946 писал(а):
от $H$ была польза и она была оптимальной
я не в силах :mrgreen:

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 21:50 
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$ - не знаю остановится или нет потому, что не могу доказать ни то ни другое.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 22:23 
tenmin в сообщении #885088 писал(а):
Хорошо, еще раз. $1$ - остановится, могу доказать это, $0$ - не остановится, могу доказать это, $-1$ - не знаю остановится или нет потому, что не могу доказать ни то ни другое.

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

tenmin в сообщении #884803 писал(а):
Короче, вопрос: существует ли такая $H$?
В любом случае, как она может не существовать - мы же ее задали тут? Уточните формулировку вопроса.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 23:22 
Аватара пользователя
patzer2097
Вы забыли ещё один случай: когда $P$ останавливается, и это не доказуемо.

 
 
 
 Re: Частичное решение halting problem
Сообщение07.07.2014, 23:28 
Munin в сообщении #885137 писал(а):
patzer2097
Вы забыли ещё один случай: когда $P$ останавливается, и это не доказуемо.

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

 
 
 [ Сообщений: 37 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group