16.01.2003
Проблема Кука
|
Ответить
11.12.2003
-
Иван Тебляшкин
Проблема Кука
Ну-ка ну-ка, попробуем... (самонадеянно так :-) ). Берем многочлен 5й степени, решения которого
не выражаются в радикалах (такие существуют по теореме Абеля). Предположительно,
x^5+2x^4+3x^3+4x^2+5x+1 является таким многочленом, по крайней мере рациональных
решений он не имеет, останется доказать, что иррациональные также не выражаются в радикалах.
А если и выражаются, то не беда - нужных многочленов все равно бесконечно много - не один,
так другой подойдет. И ставим задачу таким образом: "Доказать, что у этого многочлена существует
действительный корень". Решение: следствие из основной теоремы алгебры, т.е. решение
алгоритмизируемо и имеет конечную сложность. Проверка: кажется, единственный ее способ -
это взять конкретное число, и запихнуть его в многочлен для численной проверки. Но если
для этого многочлена известно, что его решения невыразимы в радикалах, т.е. мы не можем
просто взять и предъявить число с помощью любой комбинации цифр системы счета по
любому основанию и набора математических значков для написания операций над числами, то
проверка получится нереализуемой алгоритмически, поскольку нет алгоритма записи нужного
числа. Значит проверка также нереализуема алгоритмически, т.е. имеет бесконечную сложность.
Даже если мы найдем корень численно, то это будет только приближение решения, т.е. оно не обратит
многочлен в нуль, а будет только приближаться к нему и сойдется только за бесконечное
число итераций уточнения корня.
М-да, пока писал, сам кучу дырок в рассуждении нашел. К примеру, Абель ничего не говорил
про все элементарные функции, а только про радикалы. Ну да это не принципиально: для
какого-нибудь многочлена такой хоро-о-ошей степени наверняка тоже самое будет для всех
элементарных функций. Или и не многочлена вовсе, а любой другой задачи нахождения
непрерывной обратной функции, про которую можно доказать, что она определена в нуле. И это
вообще не доказательство, а только путь поиска: найти некую область логических утверждений,
над которой бы пересеклись утверждения существования и алгоритмической невыразимости.
Тогда решение (теорема существования) будет алгоритмизированна с конечной сложностью,
а предъявить конкретные значения для прямой проверки мы не сможем, поскольку они
алгоритмически невыразимы, т.е. проверка будет иметь бесконечную сложность.
Если у кого возникнет интересное развитие этого подхода - пишите, всегда буду рад обсудить,
а приз - пополам! :-)))
|
|
|
|