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

[tenmin]

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

Я бы только так поправил Ваше условие: $H(P)=1$ если $P$ останавливается, $H(P)=0$ если $P$ не останавливается и это доказуемо, $H(P)=-1$ если $P$ не останавливается и это не доказуемо.

Нет, так не выйдет. Такого $H$ нет. Пусть мы нашли такое $H$. Пусть $X(P)=N(H(P,P))$, где $N(1)$ и $N(-1)$ не останавливается, $N(0)$ останавливается. Значения $H(X,X)=0$ и $H(X,X)=1$ приводят к противоречию. Т.о. мы доказали, что $H(X,X)=-1$. Но тогда $X(X)=N(-1)$ не останавливается. Т.о. имеем: $X(X)$ не останавливается и это доказуемо, но $H(X,X)\neq 0$, что противоречит определению $H$.

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

Потому что обсуждать, что можете именно Вы (или еще кто-то) в рамках математической теории не получится.

Не я, а программа $H$ не может. Я не знаю как это формально сказать.

[patzer2097]

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

Нет, так не выйдет. Такого $H$ нет.

конечно. иными словами, функция $H$, заданная как

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

$H(P)=1$ если $P$ останавливается, $H(P)=0$ если $P$ не останавливается и это доказуемо, $H(P)=-1$ если $P$ не останавливается и это не доказуемо

не задается никаким алгоритмом. Это утверждение тривиально следует из неразрешимости проблемы остановки, но и Ваше доказательство тоже выглядит правильным.

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

Я не знаю как это формально сказать.

Про вычислимость и доказуемость есть книга http://www.mccme.ru/free-books/shen/she ... art3-2.pdf и доступнее, чем там, эта тема вероятно нигде не описывается

[Munin]

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

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

Вот только это конечное число шагов может быть переменным в зависимости от начальных условий. В том числе, неограниченно большим.

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

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

Нет, не годится. Тогда ваша $H(P)$ сама не остановится для неостанавливающейся $P,$ а надо, чтобы она остановилась и выдала $0$ или $-1.$

[patzer2097]

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

Вот только это конечное число шагов может быть переменным в зависимости от начальных условий. В том числе, неограниченно большим.

еще раз Вам говорю, если какой-то фиксированный алгоритм $P$ останавливается, то это происходит за конечное число шагов, описание которых и есть доказательство остановки.

(Пример)

В частности, если бы ВТФ была неверна, это было бы доказуемо средствами арифметики. Действительно, алгоритм, который перечисляет наборы $m,n,p>0$, $k>2$ и останавливается при $m^k+n^k=p^k$, остановился бы тогда на каком-то шаге

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

Нет, не годится. Тогда ваша $H(P)$ сама не остановится для неостанавливающейся $P,$ а надо, чтобы она остановилась и выдала $0$ или $-1.$

В предыдущем сообщении я пояснил, что у меня $H$ - это функция. Конечно, она никаким алгоритмом не реализуется - это тривиально следует из неразрешимости проблемы остановки

[Munin]

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

еще раз Вам говорю, если какой-то фиксированный алгоритм $P$ останавливается, то это происходит за конечное число шагов, описание которых и есть доказательство остановки.

Скажите, а если в алгоритме $P$ есть цикл, то как выглядит такое описание? А если рекурсия?

[patzer2097]

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

Скажите, а если в алгоритме $P$ есть цикл, то как выглядит такое описание? А если рекурсия?

http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf, страница 117 и далее

[Munin]

Ваше описание получится бесконечным.

[patzer2097]

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

Ваше описание получится бесконечным.

http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf, страница 123, строка 1 и далее

[Munin]

Читал. Это всё относится к арифметичности функций. Вы же заявляете другое: что это же будет доказательством. Покажите мне доказательства с бесконечным числом шагов (и при этом не по индукции) - поговорим.

[patzer2097]

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

Читал. Это всё относится к арифметичности функций. Вы же заявляете другое: что это же будет доказательством.

по приведенной ссылке описывается, как по заданному алгоритму $P$ построить формулу в PA, которая утверждает: "$P$ когда-нибудь остановится". Эта формула описывается в строках 8-24 на странице 124 и, после того как $P$ остановился, мы знаем, чему равны $n,a_1,b_1,\ldots,a_n,b_n,a,b$ и потому можем доказать эту формулу

(Munin)

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

Покажите мне доказательства с бесконечным числом шагов (и при этом не по индукции) - поговорим.

[arseniiv]

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

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

Вот-вот. А то просто бесконечное $M$ легко получить, чуточку меняя $(P,D)$. И, скорее всего, либо определение сложности будет неинтересное, либо наибольшей сложности не будет.

[Xaositect]

Munin, patzer2097. Небольшое пояснение по поводу останавливающихся функций. Вы по-моему, говорите о разных вещах. Тот факт, что алгоритм останавливается на заданном входе, если верен, то всегда доказуем. Если же говорить об алгоритмах, останавливающихся на любом входе, т.е. реализующих тотальные функции, то существуют такие алгоритмы с недоказуемой тотальностью.

[patzer2097]

Xaositect в сообщении #885589 писал(а):

Munin, patzer2097. Небольшое пояснение по поводу останавливающихся функций.

ну спасибо за пояснение

Xaositect в сообщении #885589 писал(а):

Тот факт, что алгоритм останавливается на заданном входе, если верен, то всегда доказуем.

эту банальность мы уже обсудили

Xaositect в сообщении #885589 писал(а):

Если же говорить об алгоритмах, останавливающихся на любом входе, т.е. реализующих тотальные функции, то существуют такие алгоритмы с недоказуемой тотальностью.

а эту банальность Вы зачем написали, она разве относится к делу?

[Xaositect]

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

а эту банальность Вы зачем написали, она разве относится к делу?

Я ее написал, потому как Munin, очевидно, имеет в виду именно ее:

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

Вот только это конечное число шагов может быть переменным в зависимости от начальных условий. В том числе, неограниченно большим.

[tenmin]

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

И, скорее всего, либо определение сложности будет неинтересное, либо наибольшей сложности не будет.

Да, похоже так и есть. Я понял почему то, что я хочу, не получится. Условие "$H(P,D)=-1$ когда иное значение приводит к противоречию" ссылается на $H$ будто она уже известна. Но мы её еще не закончили определять. Т.е. чтобы написать такую программу нужно чтобы она уже была написана. Иначе мы не сможем проверить это условие.