Вопрос про десятую проблему Гильберта

[fractalon]

Десятая проблема Гильберта заключается в том, чтобы найти универсальный способ решения диофантовых уравнений.
В результате исследований было доказано, что эта проблема алгоритмически неразрешима.
Вопрос. Значит ли это, что существует уравнение, для которого нельзя доказать ни наличие, ни отсутствие целочисленных решений?

[Xaositect]

Да.

[fractalon]

А где можно увидеть какое-то из таких уравнений, желательно, вмещающееся в размер монитора?

-- 12.07.2015, 23:00 --

И ещё вот что пришло в голову... А возможно ли вывести алгоритм, который будет определять, можно ли что-то сказать про данное уравнение (то есть определить наличие или отсутствие решений) или нельзя? Ведь из доказательства алгоритмической неразрешимости самой десятой проблемы ответа на этот вопрос не следует?

[Nemiroff]

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

Да.

А это значит, что поэтому у него нет корней?

Ну, видимо, да.

[Anton_Peplov]

fractalon в сообщении #1036432 писал(а):

А возможно ли вывести алгоритм, который будет определять, можно ли что-то сказать про данное уравнение (то есть определить наличие или отсутствие решений) или нельзя?

Нельзя. Потому что если бы было можно, то дальше простым перебором целых чисел для любого уравнения, имеющего целочисленное решение, это решение рано или поздно бы находилось.

[fractalon]

Nemiroff в сообщении #1036435 писал(а):

А это значит, что поэтому у него нет корней?

Вот вот, и я о том же подумал. Возможно, задаю дурацкий и типичный для начинающего позновальщика вопрос, но...
Если нельзя доказать, что у уравнения есть решение, это значит, что нельзя предъявить числа, при которых уравнение верно. А это уже, по определению, означает, что решений нет.
Или всё не так просто?

[Anton_Peplov]

fractalon в сообщении #1036419 писал(а):

Значит ли это, что существует уравнение, для которого нельзя доказать ни наличие, ни отсутствие целочисленных решений?

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

Да.

А что в этом контексте значит слово "доказать"? Вот нам предъявлено такое уравнение $u$ с $n$ переменными. Запускаем алгоритм $A$, который перебирает по порядку все упорядоченные $n$-ки целых чисел и подставляет в уравнение. Если решение есть, алгоритм остановится. Если нет - то нет.

Под "невозможно доказать" имеется в виду, что невозможен алгоритм, который определит, остановится ли $A(u)$?

[fractalon]

Anton_Peplov в сообщении #1036440 писал(а):

Нельзя. Потому что если бы было можно, то дальше простым перебором целых чисел для любого уравнения, имеющего целочисленное решение, это решение рано или поздно бы находилось.

Я спрашиваю не о том, чтобы определять наличие или отсутствие целочисленных решений, а о том, чтобы определять, можно ли установить хотя бы то или иное. Ведь, если поверить чёткому ответу Xaositect, то существует определённый класс уравнений, для которых нельзя ни то, ни другое установить. И именно этот класс мешает решению проблемы Гильберта. А можно ли каким-то образом описать этот класс, хотя бы на уровне того, чтобы придумать алгоритм, проверяющий принадлежность или непринадлежность к нему задаваемого уравнения?

-- 12.07.2015, 23:34 --

Anton_Peplov в сообщении #1036442 писал(а):

Под "невозможно доказать" имеется в виду, что невозможен алгоритм, который определит, остановится ли $A(u)$?

Всё верно, именно это и имеется в виду. Это эквивалентное утверждение.

[Anton_Peplov]

fractalon в сообщении #1036443 писал(а):

Ведь, если поверить чёткому ответу Xaositect, то существует определённый класс уравнений, для которых нельзя ни то, ни другое установить. И именно этот класс мешает решению проблемы Гильберта. А можно ли каким-то образом описать этот класс, хотя бы на уровне того, чтобы придумать алгоритм, проверяющий принадлежность или непринадлежность к нему задаваемого уравнения?

Ок. Не въехал в вопрос с первого раза.
Вопрос интересный, только обычно финт "давайте создадим алгоритм, который разделит задачи на алгоритмически разрешимые и алгоритмически неразрешимые" не прокатывает.

[Xaositect]

fractalon в сообщении #1036443 писал(а):

Я спрашиваю не о том, чтобы определять наличие или отсутствие целочисленных решений, а о том, чтобы определять, можно ли установить хотя бы то или иное. Ведь, если поверить чёткому ответу Xaositect, то существует определённый класс уравнений, для которых нельзя ни то, ни другое установить. И именно этот класс мешает решению проблемы Гильберта. А можно ли каким-то образом описать этот класс, хотя бы на уровне того, чтобы придумать алгоритм, проверяющий принадлежность или непринадлежность к нему задаваемого уравнения?

Нет, потому что в этом случае мы сможем сказать, что у уравнения корней нет. Если корни есть, это всегда можно доказать.

[epros]

fractalon в сообщении #1036441 писал(а):

Если нельзя доказать, что у уравнения есть решение, это значит...

"Нельзя доказать" и "не доказано" -- это разные вещи. То, что доказанно нельзя доказать -- опровергнуто. Но есть вещи, которые не доказаны, но и недоказуемость которых не доказана.