Распечатать запись Распечатать запись

Математическое доказательство размером с Википедию слишком большое, чтобы люди могли его проверить

Борис Конев и Алексей Лисица

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

“Вполне вероятно, что так или иначе мы столкнулись с утверждениями, которые по существу не являются человеческой математикой’’, — говорит Алексей Лисица из Ливерпульского университета, Великобритания, который придумал это доказательство вместе со своим коллегой Борисом Коневым.

Доказательство является серьезным шагом на пути к решению давно стоящей задачи, известной как проблема несоответствия Эрдёша. Эта проблема была предложена в 1930 году венгерским математиком Полом Эрдёшем, который готов был выплатить $500 за ее решение.

Представьте себе случайную бесконечную последовательность чисел, состоящую только из 1 и -1. Эрдёш был очарован тем, что такие последовательности содержат внутренние закономерности. Чтобы увидеть это, можно, например, взять конечное число членов этой последовательности, а затем создать конечные подпоследовательности в рассматриваемой части последовательности. Так, можно взять только каждое третье или каждое четвертое число.

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

Доказательство размером с Википедию

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

Довольно легко показать и без компьютера, что как бы вы ни расположили 12 плюс и минус единиц, всегда найдется подпоследовательность, сумма которой больше 1. Это означает, что все бóльшие последовательности, в том числе любые бесконечные последовательности, также должны иметь несоответствие 1 или более. Но применение этого метода для доказательства, что всегда существуют бóльшие несоответствия, сложно, так как число возможных подпоследовательностей быстро растет.

Теперь Конев и Лисица использовали компьютер, чтобы продвинуться вперед. Они показали, что бесконечная последовательность всегда будет иметь несоответствие больше, чем 2. В этом случае отсечена была последовательность из 1161 членов, а не 12. Доказательство этого потребовало почти 6 часов работы компьютера, и был сгенерирован 13-гигабайтный файл с результатами этой работы.

Это сравнимо с размерами Википедии, текст которой занимает 10 гигабайт. Это, вероятно, самое длинное доказательство. Оно превосходит другое известное огромное доказательство, которое включает 15 000 страниц вычислений.

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

Нечеловеческая математика

Гил Калай из Еврейского университета в Иерусалиме, Израиль, считает, что проверка человеком не является необходимой для принятия доказательства. “Я не обеспокоен тем фактом, что ни один математик-человек не может проверить это, потому что мы можем проверить его с помощью других компьютерных методов’’, — говорит он. Если компьютерная программа, написанная с помощью других методов, приходит к тем же результатам, то доказательство, вероятно, верное.

Калай был членом группы, которая решила в 2010 году работать над задачей в Polymath project, проекте, в котором математики используют блоги и вики для сотрудничества с большим числом людей. Запуская различное программное обеспечение, группа проверила последовательность длиной 1124. Это близко к необходимой длине последовательности, найденной Коневым и Лисицей. Однако группа сдалась, когда программа не пошла для больших чисел.

Однако, когда дело доходит до проблемы несоответствия Эрдёша, для человека есть еще некоторая надежда. Гипотеза Эрдёша состоит в том, что всегда можно найти несоответствие, равное любому числу, что очень далеко от несоответствий 1 и 2, которые сейчас были исследованы. Программное обеспечение Лисицы работает уже в течение недель в попытке найти результат для несоответствия 3. Но даже если далее компьютер покажет, что несоответствия, равные все большим числам, существуют для любой бесконечной последовательности, компьютер не может проверить бесконечно много чисел.

Вместо этого, вполне вероятно, что доказательства для конкретных значений, полученные с помощью компьютера, в конечном итоге позволят человеку найти идею и придумать доказательство для всех чисел, — по словам Лисицы. “Выдающиеся проблемы как маяки, они дают нам цели для наших возможностей’’, — добавляет Калай.

Источники: http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html?utm_medium=referral&utm_source=t.co#.Uw2nRuX3PGX

Фотография отсюда: http://www.computerra.ru/95029/the-evidence-which-validity-a-human-can-not-check/

Комментариев: 8

  1. 2 Евгений:

    Что-то не так с этим самым несоответствием. Пусть у нас последовательность из двенадцати -1, как можно выбрать из нее подпоследовательность с суммой большей 1? Или речь идет об абсолютной величине?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Я это понимаю немного не так. Должна быть хотя бы одна единица.

    [Ответить]

    Евгений Reply:

    Великолепно, берем одну единицу и одиннадцать -1, какая подпоследовательность будет иметь сумму строго больше 1?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Перечитала в источнике. Там речь идет о 12 плюсах и минусах. Видимо, нужно взять 12 единиц и 12 минус единиц.

    [Ответить]

    Евгений Reply:

    ну тогда все равно абсурд :) , взяли эти 24 числа, выбрали из них только единицы, получили сумму 12, об чем базар тогда вообще?

    [Ответить]

  2. 3 Владимир:

    А почему я перестал получать такие статьи?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Не поняла, простите. Какие статьи Вы не получаете?

    [Ответить]

Оставьте свой отзыв

Добавить изображение