PDA

View Full Version : Математические доказательства всё тяжелее проверять


DJ.
24-02-2006, 11:11
Считается, что математическое доказательство является истиной в последней инстанции. Решение, которое основано на чистой логике просто не может быть неправильным. Но с развитием науки и задачи перед математиками ставятся всё более сложные.

"Мы вошли в эпоху, когда математический аппарат стал настолько сложным и громоздким, что с первого взгляда уже нельзя сказать — правдива или нет встреченная задача", — полагает Кейт Девлин из Стенфордского Университета Калифорнии, США. Он приводит в пример "классификацию простых конечных групп", которую сформулировали еще в 1980 году, а полного точного доказательства не привели до сих пор. Скорее всего, теорема верна, но совершенно точно об этом говорить нельзя.
Компьютерное решение тоже невозможно назвать точным, ибо такие вычисления всегда имеют погрешность. В 1998 году Хейлс предложил решение при помощи компьютера теоремы Кеплера, сформулированной еще в 1611 году. Эта теорема описывает наиболее плотную упаковку шаров в пространстве. Доказательство было представлено на 300 страницах и содержало в себе 40 000 строк машинного кода. 12 рецензентов проверяли решение в течение года, но стопроцентной уверенности в правильности доказательства они так и не достигли, и исследование отправили на доработку. В результате оно было опубликовано только через четыре года и без полной сертификации рецензентов.

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

Mackintosh
24-02-2006, 15:13
а точнее... ))

matematik
24-02-2006, 17:13
можно ли для любой задачи типа "найти что-то" придумать алгоритм, который находит её решение и работает не намного медленнее, чем алгоритм, который проверяет это решение (если в Вашей формулировке некоторые слова переставить, то получится как раз то, что нужно). Короче, есть проверяющий алгоритм, нужно найти решающий алгоритм (или хотя бы проверяющий существование решения), который не намного медленее (время работы которого не более, чем полином от времени работы проверяющего).

В принципе - мы уже об этом говорили.
В теме про миллион.
Но можно и продолжить.
Поскольку интересно.

И просьба - к DJ.
Может, стоит давать ссылку на источник?
Или вопрос задавать - в чем предмет восхищения-то?

Канарейка
24-02-2006, 17:15
А что ж вы хотите, что попроще уже более "ловкие" доказали...
Эх, тяжела жизнь современного человека!

DJ.
24-02-2006, 17:24
Может, стоит давать ссылку на источник?
Или вопрос задавать - в чем предмет восхищения-то?

http://science.compulenta.ru/253954/

А что чтобы создать тему надо обязательно ей восхищаться?? :)

matematik
24-02-2006, 17:45
http://science.compulenta.ru/253954/

А что чтобы создать тему надо обязательно ей восхищаться?? :)
Не, не обязательно.
Это был просто вопрос на понимание.
Приведенной Вами ссылки вполне достаточно.
Спасибо.

Бегемот
24-02-2006, 22:56
Считается, что математическое доказательство является истиной в последней инстанции. Решение, которое основано на чистой логике просто не может быть неправильным. Но с развитием науки и задачи перед математиками ставятся всё более сложные.

Не только перед ними.

"Мы вошли в эпоху, когда математический аппарат стал настолько сложным и громоздким, что с первого взгляда уже нельзя сказать — правдива или нет встреченная задача", — полагает Кейт Девлин из Стенфордского Университета Калифорнии, США. Он приводит в пример "классификацию простых конечных групп", которую сформулировали еще в 1980 году, а полного точного доказательства не привели до сих пор. Скорее всего, теорема верна, но совершенно точно об этом говорить нельзя.

Да ну? А удвоение куба, трисекция угла, большая теорема Ферма - это все уже после 80 го?

Компьютерное решение тоже невозможно назвать точным, ибо такие вычисления всегда имеют погрешность.

Компьютерное решение вообще не есть доказательство. Как и графическое, например.

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

To matematik
"Короче, есть проверяющий алгоритм, нужно найти решающий алгоритм (или хотя бы проверяющий существование решения), который не намного медленее (время работы которого не более, чем полином от времени работы проверяющего)."

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

DJ.
27-02-2006, 19:36
Да ну? А удвоение куба, трисекция угла, большая теорема Ферма - это все уже после 80 го?



Большая Теорема Ферма доказана уже 10 лет назад :) Там вроде речь шла про те что еще не доказаны :)

Бегемот
27-02-2006, 20:50
Большая Теорема Ферма доказана уже 10 лет назад :) Там вроде речь шла про те что еще не доказаны :)
Простите за невежество, а ссылку можно?

DJ.
27-02-2006, 20:55
Простите за невежество, а ссылку можно?

Можно, только уточните ссылку на что :)

ank
27-02-2006, 23:01
Простите за невежество, а ссылку можно?
http://fermats-last-theorem.brainsip.com/
http://en.wikipedia.org/wiki/Fermat%27s_last_theorem