загадочная сложность теории чисел

[avva]

The enigmatic complexity of number theory

Вопрос, который я сам себе не раз задавал, но насчет которого я тем не менее не уверен в том, насколько он осмыслен и интересен. Теория чисел - часть математики, которая изучает свойства целых чисел - вроде бы выделяется на фоне всех других математических дисциплин феноменальным количеством задач, которые просто сформулировать, но сложно решить. Сюда конечно относятся теорема Ферма и другие очень простые по формулировке и еще не решенные проблемы (гипотеза Гольдбаха: любое четное число можно представить в виде суммы двух простых; гипотеза о простых числах-близнецах, гипотеза Коллатца). Но по-моему дело не только в нерешенных или супер-тяжелых проблемах; теория чисел поражает также тем, как очень простые по формулировке утверждения требуют для своего доказательства "тяжелой артиллерии" из казалось бы, наивно говоря, более продвинутых областей математики.

В обсуждении по ссылке Скотт Ааронсон предлагает следующий ответ: арифметических действий с целыми числами достаточно, чтобы воплотить любой возможный алгоритм; отсюда следует, что уже даже относительно простые утверждения о целых числах могут упираться в фундаментальные ограничения типа "это невозможно доказать в принципе": теоремы Геделя о неполноте, неразрешимость проблемы остановки итп. Таким образом, в теории чисел неразрешимые задачи лежат буквально за углом, и расстояние о тривиальных фактов до них относительно невелико. Поэтому быстро приходят к сложным вопросам, которые еще разрешимы (скорее всего), но уже близки к неразрешимым.

Не уверен, что мне нравится этот ответ: то, что диофантовы уравнения упираются в неразрешимость в общем виде, это одно; а то, что мы не знаем, как решать даже очень просто выглядящие такие конкретные уравнения (пример из обсуждения: x^3+y^3 = z^3+33, неизвестно, есть ли решение у этого уравнения в целых числах) - другое, и мне не кажется очевидным, что эти две сложности друг с другом связаны. Но другого ответа у меня нет. Более того, нет даже уверенности, что этот вопрос осмыслен - возможно, это артефакт того, как мы определяем различные дисциплины в математике и то, что в них считается базисным-тривиальным?

Comments

[dims12.livejournal.com]

Иными словами. Мы знаем, что любое целочисленное уравнение можно решить путём перебора, но перебрать надо бесконечное количество чисел. Предположение о том, что ВСЕГДА можно сократить эту задачу до конечного числа шагов, имеет, скорее всего, отрицательный ответ. Соответственно, ДОЛЖНО существовать сколько угодно много целочисленных задач, которые можно решить ТОЛЬКО бесконечным перебором. По теореме Геделя, распознать такую ситуацию нельзя, то есть, если мы такую задачу найдём, то будем над ней биться и либо в какой-то момент будем находить более короткий путь, либо не будем.

[(Anonymous)]

Ну знаете, количество разрешимых задач вообще счетное.

Каждая разрешимая задача имеет ответом конструктивное число, которых тоже счетное количество.

Так что любую разрешимую задачу "можно решить перебором, ТОЛЬКО бесконечным".

И что нам это дает в качестве добавленной стоимости?

[dims12.livejournal.com]

Я не брал разрешимые задачи, я брал любую целочисленную задачу, включая неразрешимые.

[(Anonymous)]

Это ничего не меняет. Задача - это конечный текст в конечном алфавите, то есть задач - счетное множество.

[dims12.livejournal.com]

Квадратных уравнений -- тоже счётное множество?

[(Anonymous)]

Если допускать неконструктивные коэффициенты - то и линейных уравнений континуум.

Только беда в том, что такое уравнение существует только в смысле теоремы существования и никак не может быть сформулировано более конкретно.

То есть, в известном смысле, не является задачей или ее составной частью.

******************

Только не подумайте, что я адепт конструктивной математики. Вовсе нет. Но слово "задача" понимаю не так общо, как вы.

[dims12.livejournal.com]

> уравнение существует только в смысле теоремы существования и никак не может быть сформулировано более конкретно

Ну тогда и вещественных чисел не существует "конкретно", а только в виде существования :)

[livelight]

Любое вещественное число может быть представлено в виде бесконечной последовательности цифр. Это вполне конкретно :) Но в задачу (которая является конечным текстом) вы его в таком виде вставить не сможете, а сможете только такое число, которое сможете закодировать (в угодной вам системе кодирования, где никто не запретит, например, использовать знак pi, но о системе кодирования придётся договориться заранее) конечным текстом.

[(Anonymous)]

Именно так все и происходит - нет никакого сомнения в существовании действительных чисел, но конструктивных среди них - всего лишь счетное множество.

Так что думать о них можно, а вот использовать в задачах не получится. Просто потому, что не получится сформулировать задачу. [а если получится - значит ошибка в консерватории и число конструктивное]

[dims12.livejournal.com]

P.S. Например, упомянутая задача

x^3+y^3 = z^3+33

Допустим, она неразрешима. Но если перебрать все возможные числа x, y, z, коих бесконечное число, то она будет разрешена.

[(Anonymous)]

Ага, именно так. Ограничение на время решения задачи введено математиками по вполне понятным причинам. Но это внематематическое ограничение, поскольку вычисления это физический процесс, который оперирует с абстрактными сущностями.

Не слушайте этих чёкнутых....

[андрей лощинин (from livejournal.com)]

Бредятина понаписана полнейшая.
Если ты не можешь решить уравняшку - то это ни в коем случае не означает, что её нельзя решить.
С другой стороны неопределённые алгебраические уравняшки такая штука, что чем больше там неизвестных - тем легче оно решается...
И это можно использовать. Заменить это уравнение на другое. А потом перейти к тем числам которые нам нужны.
Оставьте перебор в покое. Очень многое можно просто решить.