Hilbert's 10th Problem Reloaded
Jan. 17th, 2013 05:12 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
leblonСходил вчера на лекцию Бьорна Пунена про 10ю проблему Гильберта и ее обобщения. Уровень был для undergraduates, так что я вроде все понял. Сначала он "объяснил" теорему Davis-Putnam-Roberts-Матиясевича из которой следует, что ответ на 10ю проблему Гильберта отрицательный. Т.е. почему не может быть алгоритма, который решает, когда полиномиальное уравнение с целыми коэффициентами имеет целое решение. Сначала Пунен дал два определения: диофантова подмножества и перечислимого подмножества. Диофантово подмножество Х множества целых чисел Z - это такое множество, которое получается проекцией множества значений какого нибудь полинома с целыми коэффициентами в целых точках на одну из координатных осей. Перечислимое подмножество - это подмножество, которое может "выдать" машина Тьюринга следуя какой нибудь программе. Очевидно, что любое диофантово подмножество перечислимо. DPRM доказали, что обратное тоже верно: любое перечислимое подмножество диофантово. С другой стороны, давно известно, что бывают такие перечислимые множества, что не существует алгоритма, который ответит, приндалежит ли данное число этому множеству или нет. (Это следует, например, из отрицательного решения halting problem). Из этих двух результатов и вытекает отрицательный ответ на 10ю проблему Гильберта.
А теперь заменим кольцо целых чисел на другое какое-нибудь кольцо. Изменится ли ответ? Если спрашивать про разрешимость уравнения (опять с целыми коэффициентами, для простоты) в комплексных, или вещественных, или даже p-адических числах, то ответ будет другой! Т.е. для таких колец алгоритм есть. А вот для кольца рациональных чисел Q ответ неизвестен! Т.е. может быть существует алгоритм для того, чтобы решить, разрешимо ли любое полиномиальное уравнение в рациональных числах. А может и не существует.
Наивная интуиция, вроде, говорит нам, что случай Q не должен существенно отличаться от случая Z. Т.е. хочется свести задачу к уже известной теореме DPRM. Но для этого надо доказать, что множество Z "диофантово над Q". Т.е. что существует полином с целыми коэффициентами, проекция значений которого в рациональных точках на одну из осей это в точности множество Z. А это, судя по всему, не так, хотя никто этого пока не доказал. На самом деле, есть даже более общая гипотеза Мазура, которая говорит,. что замыкание любого подмножества вещественных чисел, диофантова над Q, имеет конечное число компонент связности. Конечно, как это доказать тоже никто не знает.
Пунен говорил немного и про другие интересные кольца (рациональные функции, числовые поля), но что именно, я забыл.
А теперь заменим кольцо целых чисел на другое какое-нибудь кольцо. Изменится ли ответ? Если спрашивать про разрешимость уравнения (опять с целыми коэффициентами, для простоты) в комплексных, или вещественных, или даже p-адических числах, то ответ будет другой! Т.е. для таких колец алгоритм есть. А вот для кольца рациональных чисел Q ответ неизвестен! Т.е. может быть существует алгоритм для того, чтобы решить, разрешимо ли любое полиномиальное уравнение в рациональных числах. А может и не существует.
Наивная интуиция, вроде, говорит нам, что случай Q не должен существенно отличаться от случая Z. Т.е. хочется свести задачу к уже известной теореме DPRM. Но для этого надо доказать, что множество Z "диофантово над Q". Т.е. что существует полином с целыми коэффициентами, проекция значений которого в рациональных точках на одну из осей это в точности множество Z. А это, судя по всему, не так, хотя никто этого пока не доказал. На самом деле, есть даже более общая гипотеза Мазура, которая говорит,. что замыкание любого подмножества вещественных чисел, диофантова над Q, имеет конечное число компонент связности. Конечно, как это доказать тоже никто не знает.
Пунен говорил немного и про другие интересные кольца (рациональные функции, числовые поля), но что именно, я забыл.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2013-01-18 01:39 am (UTC)(no subject)
Date: 2013-01-18 01:50 am (UTC)(no subject)
Date: 2013-01-18 01:53 am (UTC)(no subject)
Date: 2013-01-18 09:48 am (UTC)(no subject)
Date: 2013-01-18 01:59 am (UTC)Что же до самого вопроса, то мне лично это кажется чистой схоластикой, вроде подсчета числа ангелов на кончике иглы. Никакого практического смысла в отрицательном результате нет, если нас интересуют собственно решения диофантовых уравнений. Если бы не авторитет Гильберта, уверен, что никакого ажиотажа по поводу именно этого вопроса не было бы. Впрочем, это мое мнение, настаивать не стану.
(no subject)
Date: 2013-01-18 05:14 am (UTC)(no subject)
Date: 2013-01-18 07:44 am (UTC)Последний шаг, сделанный Матиясевичем в доказательстве ДПРМ вообшем-то элементарный. Вспомнил одно свойство чисел фибоначчи, про которое никто не подумал.
Формулировка 10 проблемы как собственно поиск решений таки неинтересна.
Но отрицательный результат - лишь побочное следствие совершенно могучего факта о диофантовости всех множеств.
Кстати, говорить о том, что результат ДПРМ зависит от других результатов о существовании неразрешимых множеств (Тьюринг, Гедель) - методически неверно. Диагонализатсия достигается за счет того, что множество всех диофантовых уравнений - диофантово, значит содержит свое представление. Тот же тьюринговский фокус, но без лишних фокусов :)
(no subject)
Date: 2013-01-18 09:50 am (UTC)Там же положительный результат имеется: что всякое перечислимое мн-во диофантово. Вот это, по-моему, красиво и интересно.
(no subject)
Date: 2013-01-18 02:23 pm (UTC)вот, что рассказывает Мартин Девис
http://www.cs.nyu.edu/pipermail/fom/1998-February/001172.html
(no subject)
Date: 2013-01-18 02:58 pm (UTC)http://www.mathnet.ru/links/c3224c3a70d845080d6e121197101e55/rm5380.pdf
http://www.mathnet.ru/links/0bd086fc5c179cfe131874697b6833b9/rm5387.pdf
(и то, и другое - из "Успехов математических наук" номер 4 за 1970 год). Ср. с рассказом Девиса.
Всей правды мы, надо полагать, никогда не узнаем.
(no subject)
Date: 2013-01-18 05:25 pm (UTC)Здесь еще упоминаются некоторые даты, для сравнения
http://logic.pdmi.ras.ru/~yumat/Julia/
(no subject)
Date: 2013-01-18 07:37 pm (UTC)(no subject)
Date: 2013-01-18 08:26 pm (UTC)(no subject)
Date: 2013-01-18 08:46 pm (UTC)(no subject)
Date: 2013-01-18 10:01 am (UTC)(no subject)
Date: 2013-01-18 03:28 pm (UTC)