2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 02:00 
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$ не может. Я не знаю как это формально сказать.

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 03:10 
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 и доступнее, чем там, эта тема вероятно нигде не описывается :-)

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 11:22 
Аватара пользователя
patzer2097 в сообщении #885139 писал(а):
Такого случая нет: если $P$ останавливается, то это происходит за конечное число шагов алгоритма.

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

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

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

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 14:17 
Munin в сообщении #885236 писал(а):
Вот только это конечное число шагов может быть переменным в зависимости от начальных условий. В том числе, неограниченно большим.
еще раз Вам говорю, если какой-то фиксированный алгоритм $P$ останавливается, то это происходит за конечное число шагов, описание которых и есть доказательство остановки.

(Пример)

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


Munin в сообщении #885236 писал(а):
Нет, не годится. Тогда ваша $H(P)$ сама не остановится для неостанавливающейся $P,$ а надо, чтобы она остановилась и выдала $0$ или $-1.$
В предыдущем сообщении я пояснил, что у меня $H$ - это функция. Конечно, она никаким алгоритмом не реализуется - это тривиально следует из неразрешимости проблемы остановки :-)

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 15:23 
Аватара пользователя
patzer2097 в сообщении #885338 писал(а):
еще раз Вам говорю, если какой-то фиксированный алгоритм $P$ останавливается, то это происходит за конечное число шагов, описание которых и есть доказательство остановки.

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

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 15:49 
Munin в сообщении #885358 писал(а):
Скажите, а если в алгоритме $P$ есть цикл, то как выглядит такое описание? А если рекурсия?
http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf, страница 117 и далее

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 16:06 
Аватара пользователя
Ваше описание получится бесконечным.

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 16:24 
Munin в сообщении #885374 писал(а):
Ваше описание получится бесконечным.
http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf, страница 123, строка 1 и далее :twisted:

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 17:20 
Аватара пользователя
Читал. Это всё относится к арифметичности функций. Вы же заявляете другое: что это же будет доказательством. Покажите мне доказательства с бесконечным числом шагов (и при этом не по индукции) - поговорим.

 
 
 
 Re: Частичное решение halting problem
Сообщение08.07.2014, 17:56 
Munin в сообщении #885402 писал(а):
Читал. Это всё относится к арифметичности функций. Вы же заявляете другое: что это же будет доказательством.
:twisted: по приведенной ссылке описывается, как по заданному алгоритму $P$ построить формулу в PA, которая утверждает: "$P$ когда-нибудь остановится". Эта формула описывается в строках 8-24 на странице 124 и, после того как $P$ остановился, мы знаем, чему равны $n,a_1,b_1,\ldots,a_n,b_n,a,b$ и потому можем доказать эту формулу :twisted:

(Munin)

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

 
 
 
 Re: Частичное решение halting problem
Сообщение09.07.2014, 01:32 
tenmin в сообщении #885088 писал(а):
Хотя нет, не то. Надо другое условие. По сложности $M$. Нужно $H$ c самым сложным $M$ (если оно есть). Надо определить, что значит "сложность $M$" и доказать, что есть верхняя граница.
Вот-вот. А то просто бесконечное $M$ легко получить, чуточку меняя $(P,D)$. И, скорее всего, либо определение сложности будет неинтересное, либо наибольшей сложности не будет.

 
 
 
 Re: Частичное решение halting problem
Сообщение09.07.2014, 02:15 
Аватара пользователя
Munin, patzer2097. Небольшое пояснение по поводу останавливающихся функций. Вы по-моему, говорите о разных вещах. Тот факт, что алгоритм останавливается на заданном входе, если верен, то всегда доказуем. Если же говорить об алгоритмах, останавливающихся на любом входе, т.е. реализующих тотальные функции, то существуют такие алгоритмы с недоказуемой тотальностью.

 
 
 
 Re: Частичное решение halting problem
Сообщение09.07.2014, 02:34 
Xaositect в сообщении #885589 писал(а):
Munin, patzer2097. Небольшое пояснение по поводу останавливающихся функций.
ну спасибо за пояснение :twisted:
Xaositect в сообщении #885589 писал(а):
Тот факт, что алгоритм останавливается на заданном входе, если верен, то всегда доказуем.
эту банальность мы уже обсудили :twisted:
Xaositect в сообщении #885589 писал(а):
Если же говорить об алгоритмах, останавливающихся на любом входе, т.е. реализующих тотальные функции, то существуют такие алгоритмы с недоказуемой тотальностью.
а эту банальность Вы зачем написали, она разве относится к делу? :twisted:

 
 
 
 Re: Частичное решение halting problem
Сообщение09.07.2014, 02:36 
Аватара пользователя
patzer2097 в сообщении #885595 писал(а):
а эту банальность Вы зачем написали, она разве относится к делу? :twisted:
Я ее написал, потому как Munin, очевидно, имеет в виду именно ее:
Munin в сообщении #885236 писал(а):
Вот только это конечное число шагов может быть переменным в зависимости от начальных условий. В том числе, неограниченно большим.

 
 
 
 Re: Частичное решение halting problem
Сообщение09.07.2014, 03:44 
arseniiv в сообщении #885578 писал(а):
И, скорее всего, либо определение сложности будет неинтересное, либо наибольшей сложности не будет.

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

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


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