avva: (Default)
[personal profile] avva
Тема возникла в комментариях вот здесь. [livejournal.com profile] french_man подробно описал своё (положительное) отношение к использованию компьютерных программ в математических доказательствах здесь (два коммента), за что ему большое спасибо. Я опрометчиво пообещал сделать то же самое: пришлось основательно подумать, чтобы понять, какова же собственно моя позиция по этому поводу. Надумалось довольно много.

Итак, речь идёт о математических теоремах (или, более обще и неопределённо, результатах), в процессе доказательства (получения) которых нетривиальным образом используются компьютерные программы. Уточним: речь идёт о теоремах в "чистой" математике, не требующих априори длинных вычислений (в конце концов, "найдите первый миллион цифр в десятичном разложении пи" тоже ведь математическая задача). Более важно уточнить, что значит "нетривиальным образом": это значит, что заменить запуск программы ручной проверкой не представляется возможным (скажем, такая проверка заняла бы миллион лет).

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

Все известные доказательства этой теоремы используют компьютерные программы нетривиальным образом. Впервые её доказали Аппель и Хакен в 1976-м году, а недавно было опубликовано новое, более простое доказательство. В обоих случаях доказательство состоит из теоретической части, в которой доказываются некоторые свойства, которыми обязан обладать контрпример, опровергающий теорему (а именно: он должен содержать в себе конфигурацию специального вида, и всего таких возможных конфигураций конечное количество), и компьютерной части, в которой вполне нетривиальный алгоритм перебирает это конечное кол-во конфигураций и проверяет, что ни одна из них не "подходит" для включения в контрпример (я здесь немного упростил, но несущественно).

О доказательствах такого рода можно задать два вопроса:

1. Насколько стоит им доверять? Должны ли они иметь такой же статус, как "обычные" доказательства? Каковы аргументы за или против использования таких доказательств?

Это вопрос философский, относящийся к философии математики.

2. Как к ним в действительности относятся в математическом сообществе? Как к ним относятся математики и какие аргументы выдвигают в поддержку своих мнений?

Это вопрос социологический.

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

[livejournal.com profile] french_man предлагает следующий достаточно убедительный список выдвигаемых обычно причин "против" -
а) Формальные: Нет абсолютной точности, т.к. она недостижима в физическом мире (компьютеры ломаются, электроны управляются вероятностями).
б) Концептуальные: Такие доказательства "механичны", не добавляют ничего к нашему пониманию математики.
в) Психологические: неуютно.

- и отвергает их одну за другой. С его возражениями я в принципе согласен, и согласен с тем, что это причины обычно выдвигаемые (вопрос номер 2 выше), но не согласен с тем, что это все возможные причины "быть против" (вопрос номер 1 выше). К особо интересующему меня аргументу можно придти только путём пристального анализа этих, уже выдвинутых, причин.

"Концептуальный" аргумент меня не очень интересует, и принципиальным, на мой взгляд, не является. Не буду на нём останавливаться. "Психологический" аргумент сам по себе аргументом не является - это констатация факта. Математикам "не нравятся" такие доказательства, им неуютно с ними. Но почему не нравятся? - это нужно пытаться объяснить отдельно. Остаётся "формальный" аргумент, кстати, по моему опыту, как раз наиболее часто встречающийся.

А: Я не доверяю компьютеру. Компьютеры ошибаются.
Б: В каком смысле ошибаются?
А: В прямом. Как может моя вера в правильность доказательства зависеть от того, что какая-то там проволока правильно соединилась с другой проволокой и не соскочила?
Б: Но ведь математики тоже ошибаются. Причём постоянно и, пожалуй, куда чаще компьютеров.
А: Ну это потому что они и задачи выполняют куда сложнее компьютерных! И вообще, это другое.
Б: Но почему другое?
А: Не знаю. Но чувствую. Может быть, вот почему: математик сам отвечает за свои ошибки. Это его проблемы, и в идеале, если он постарается, он их обнаружит.
Б: Посадим параллельно компьютер и математика перемножать много 200-значных чисел. Кто больше раз ошибётся? Ответ очевиден. В конце концов, просто с прагматической точки зрения стоит доверять компьютеру. А чувства-шмувства... это просто от привычки. Привыкнем доверять компьютерам - и интуиция изменится.

В этом диалоге А - некий общий образ математика, настроенного "против" компьютерных доказательств, а Б - математика, настроенного "за", и использующего примерно те же аргументы, что высказал [livejournal.com profile] french_man. Оба математика, однако, упускают одну важную деталь. Какую?

Мы доверяем не компьютеру, а алгоритму.

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

1. Мы доверяем алгоритму, составленному для решения задачи. Это значит, что мы верим в то, что алгоритм действительно правильно её решает. Алгоритм - математический объект.
2. Мы доверяем инженерам, сконструировавшим компьютер. Это значит, что мы верим в то, что компьютер безошибочно выполняет алгоритм. Компьютер - физическое устройство.

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

Давайте убедимся в том, что первая составляющая действительно существует и реальна. Вопрос: почему математик не боится умножать в столбик? Ведь умножение в столбик - это тоже алгоритм, во время выполнения которого думать не надо, а надо глупо следовать правилам. Ответ: потому что математик доверяет алгоритму. Он знает (и может строго доказать), что если взять число X и число Y, и провести с их десятичными представлениями некоторое количество странных сложений, сдвигов и переносов "в уме", то получится десятичное представление числа X*Y. Именно это знание даёт ему основания не задумываться над проблемой умножения в столбик. Если бы он не доверял алгоритму, неважно было бы, кто бы собственно выполнял алгоритм - он сам в уме, он сам на бумаге или компьютерная программа - результату он бы всё равно не поверил.

Теперь становится понятней, что упускают А и Б, и в чём упущение "формального аргумента". Все выдвигаемые возражения против компьютера относятся ко второй, физической фазе.

Все эти "вероятностные электроны" и "ошибки CPU" - детали физического воплощения. Стоит ли "доверять" им? Это всё ещё нетривиальный вопрос, но стандартный ответ на него теперь приобретает несколько большую силу. Стандартный ответ таков: мы можем повторить вычисление тысячи раз и проверить, что получаем один и тот же результат. "Железо" сбоит? Так мы запустим его на десятках разных компьютеров разных архитектур. Компилятор может содержать ошибку? Перепишем алгоритм на десятке других языков программирования и пропустим через десять других компиляторов.

Мы можем объективно оценить вероятность "сбоя" компьютера/компилятора/экрана/проводки и путём независимых повторов такого рода сделать её сколь угодно малой. Сколь угодно, но не нулём - возражает А! Что ж, он прав. Но когда эта вероятность становится ниже вероятности спонтанного превращение Солнца в суперновую звезду в ближайшие пять минут, например, это кажется не столь уж важным. Особенно учитывая первую, математическую фазу доверия, о которой А до сих пор не задумался.

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

Каковы же эти проблемы? Доверяем же мы, действительно, алгоритму умножения в столбик! Почему бы не доверять алгоритму, который помогает нам доказать теорему четырёх цветов? Об этом - в следующей записи, уже утром.

Ïî ïîâîäó ïîñòîâ aculeata è sova

Date: 2001-09-10 09:56 am (UTC)
From: [identity profile] french-man.livejournal.com
Âñå âåðíî. Íàäî ñòðåìèòüñÿ ê åñòåñòâåííîñòè è êîíöåïòóàëüíîñòè. Ëèøü êîíöåïòóàëüíûå äîêàçàòåëüñòâà ïðîÿñíÿþò ñóòü âåùåé. Íî âîçíèêàþò òðè âîïðîñà.

(à) À ÷òî òàêîå êîíöåïòóàëüíîå äîêàçàòåëüñòâî?
(á) Êàê äîñòèãàòü êîíöåïòóàëüíîñòè?
(â) Âñåãäà ëè êîíöåïòóàëüíîñòü äîñòèæèìà?


Ýòî òàêæå îôôòîïèê, íî âñå æ ïîïûòàþñü âûñêàçàòüñÿ.

(à) Êîãäà ãîâîðÿò, ÷òî íåêîå ðàññóæäåíèå êîíöåïòóàëüíî, à äðóãîå íåò, âñåãäà ñëåäóåò ñïðîñèòü: äëÿ êîãî êîíöåïòóàëüíî? Ðåøåíèå òðóäíîé çàäà÷è âñåãäà êîíöåïòóàëüíî äëÿ åãî ñîçäàòåëÿ. Íåâîçìîæíî ñäåëàòü ÷òî–ëèáî íåòðèâèàëüíîå, íå èìåÿ êîíöåïöèè. Áåñêîíöåïòóàëüíû ëèøü ïóñòûå îáîáùåíèÿ è ïðî÷èå äèññåðòàáåëüíîñòè. Äðóãîå äåëî, ÷òî òðóäíîñòü çàäà÷è è/èëè ýêñïîçèòîðñêàÿ áåçäàðíîñòü àâòîðà ìîãóò ïðèâåñòè ê èñ÷åçíîâåíèþ ëåñà êîíöåïòóàëüíîñòè çà äåðåâüÿìè ïðîìåæóòî÷íûõ òåõíè÷åñêèõ ðåçóëüòàòîâ.

Ýòî çàìå÷àíèå, ïðàâäà, îòíîñèòñÿ èìåííî ê áåñêîìïüþòåðíûì äîêàçàòåëüñòâàì. Êîìïüþòåðíûé ñ÷åò, äåéñòâèòåëüíî, îáû÷íî óäðó÷àþùå áåñêîíöåïòóàëåí. Òàê æå áåñêîíöåïòóàëüíîé ìîæåò îêàçàòüñÿ ðó÷íàÿ ïðîâåðêà êàêèõ–íèáóäü ñëó÷àåâ, íå ïîäïàäàþùèõ ïîä îáùåå ðàññóæäåíèå. Îá ýòîì ñì. (â).

(á) Êîíå÷íî, Ãðîòåíäèê óñòàìè [livejournal.com profile] aculeata ãëàãîëåò èñòèíó:
êîãäà ïðîáëåìà ïîíÿòà âïîëíå è âçÿòà îòòóäà, ãäå îíà äåéñòâèòåëüíî ëåæèò, äîêàçàòåëüñòâî òèïà ñàìî ïîä íîãè ïàäàåò. Ñäîõíó è ò.ä.

Âîïðîñ â òîì, êàê åå ïîíÿòü? Ìîæíî, êàê Ãðîòåíäèê, ðàçâèâàòü îáùóþ òåîðèþ âñåãî. Ýòîò ïîäõîä, â óìåëûõ ðóêàõ, ìîæåò áûòü ÷ðåçâû÷àéíî ïëîäîòâîðíûì.  íàøóìåâøåì â 70–å ãîäû ñïîðå Ìîðäåëëà–Çèãåëÿ è Ëåíãà ÿ ïîëíîñòüþ íà ñòîðîíå ïîñëåäíåãî.

ß æå, â ñèëó íåäîñòàòêà îáðàçîâàíèÿ, è íåêîòîðûõ ëè÷íûõ êà÷åñòâ, ïðåäïî÷èòàþ ïðèìèòèâíî–àãðåññèâíûé ïîäõîä. Ðåøàòü, òèïà, çàäà÷êó, íå çàáîòÿñü î ãëîáàëüíûõ êîíöåïöèÿõ. Ïîñëåäíèå ïðèäóò. Ïîäõîä "ìûøèíîé íîðû" ïî Ãóìèëåâó. Ðàçóìååòñÿ, íîðà ìîæåò îáâàëèòüñÿ è çàäàâèòü òåõ, êòî ïîñëåäîâàë çà ïðîðûâøèì åå. À ìîæåò è ñòàòü íà÷àëîì øèðîêîãî òîííåëÿ ñî ñâåòîì â êîíöå. Ïðîñòèòå áàíàëüíîñòü îáðàçîâ.

(â) À ïî÷åìó, ñîáñòâåííî, êîíöåïòóàëüíîñòü âñåãäà äîñòèæèìà? Ñîãëàñíî "êîëè÷åñòâåííîé" òåîðåìå Ãåäåëÿ, âûâîä âûâîäèìîé ôîðìóëû ìîæåò áûòü ñêîëü óãîäíî äëèííåå åå ñàìîé. Ò.å., äàæå åñëè òåîðåìà äîêàçóåìà, åå äîêàçàòåëüñòâî ìîæåò áûòü ñêîëü óãîäíî ñëîæíåå ôîðìóëèðîâêè.

Âîçìîæíîñòè ÷åëîâå÷åñêîãî ìîçãà îãðàíè÷åíû, òàê æå êàê è åãî ôèçè÷åñêèå âîçìîæíîñòè. Äîïóñêàþ, ÷òî êîãäà–íèáóäü ÷åëîâåê ïðûãíåò íà 3 ìåòðà â âûñîòó. Íî íà 30 – íèêîãäà. ×òîáû ïîäíÿòüñÿ íà 30 ìåòðîâ, íóæíà âåðåâêà èëè âåðòîëåò.

Òàê æå è çäåñü. Íå èñêëþ÷àþ, ÷òî ÷åëîâå÷åñêèé ìîçã íå â ñîñòîÿíèè óâèäåòü êîíöåïöèþ, ñïðÿòàííóþ çà êàêîé–íèáóäü âåðèôèêàöèåé, íå ïîòîìó, ÷òî òàì ýòîé êîíöåïöèè íåò, à ïîòîìó, ÷òî îíà ñëèøêîì ñëîæíà è íàøåìó ìîçãó íåäîñòóïíà. Òàê ÷òî ðàññóæäàòü, ïðèíàäëåæèò ëè íåêîå ä–âî the Book, íà ìîé âçãëÿä, íåïðàâîìåðíî. Ýòî ðåøàåì íå ìû, à Òoò, êòî ïèøåò the Book.

À ðàç òàê, òî óæ ëó÷øå èìåòü êîìïüþòåðíîå ä–âî, ÷åì íèêàêîãî. Ïðèíöèï áåçðûáüÿ, òèïà.

Ñ óâàæåíèåì,

Ôðàíöóçèê.
From: [identity profile] sova.livejournal.com
Ðàññóæäàòü ìîæåò è íåò, à âîò ðåøàòü - äà, èáî às for everything else, so for a mathematical theory: beauty can be perceived but not explained. (Arthur Cayley)

Êñòàòè, ñàì Ýðäîø íåîäíîêðàòíî ïîïðàâëÿë â òîì äóõå, ÷òî the Book, êîíå÷íî, åñòü, à âîò íàñ÷¸ò Òîãî îí íèêîãäà íè÷åãî íå ãîâîðèë è âîîáùå íå óâåðåí :-).
From: [identity profile] french-man.livejournal.com
Êñòàòè, ñàì Ýðäîø íåîäíîêðàòíî ïîïðàâëÿë â òîì äóõå, ÷òî the Book, êîíå÷íî, åñòü, à âîò íàñ÷¸ò Òîãî îí íèêîãäà íè÷åãî íå ãîâîðèë è âîîáùå íå óâåðåí :-).

Åùå êàê ãîâîðèë. Êîãäà ÿ ïîìðó, òèïà, ÿ ó íåãî ñïðîøó, è ò.ä.

 îáùåì–òî, ÿ ñ Âàìè ñîãëàñåí. ß òîæå ïðåäïî÷èòàþ êðàñèâîå è êîíöåïòóàëüíîå. È ñòàðàþñü âñå äåëàòü êðàñèâî è êîíöåïòóàëüíî. Íî íå ñ÷èòàþ ýòî ñàìîöåëüþ. Ò.å. åñëè êîíöåïòóàëüíî íå ïîëó÷àåòñÿ, äåëàþ, êàê ïîëó÷àåòñÿ.

Ñ óâàæåíèåì,

Ôðàíöóçèê.

Ï.Ñ. Ïðàâèëüíåå "Ýð䏸".
From: [identity profile] sova.livejournal.com
Óòî÷íÿåì. Öèòàòà èç Joel Spencer, êîòîðûé ðàññêàçûâàåò îò ïåðâîãî ëèöà:

In my introduction to his [Pál Erdős] lecture I discussed The Book but I made the mistake of discribing it as being “held by God”. Paul began his lecture with a gentle correction that I shall never forget. “You don't have to believe in God,” he said, “but you should believe in The Book.”
From: [identity profile] french-man.livejournal.com
Âåðíî. ß âîâñå íå óòâåðæäàþ, ÷òî Uncle Paul áûë ðåëèãèîçíûì ÷åëîâåêîì. Óæ ñ îáðÿäîâîé òî÷êè çðåíèÿ, òî÷íî íå áûë.

Íî ýòà ôðàçà â äàííîì êîíòåêñòå íè÷åãî íå çíà÷èò. Òî÷íåå ãîâîðÿ, îíà çíà÷èò ëèøü òî, ÷òî îíà çíà÷èò: äëÿ âåðû â Book íå íàäî âåðèòü â Á–ãà. Íî îíà íèêàê íå ìîæåò ñëóæèòü àðãóìåíòîì â ïîëüçó íåâåðèÿ ñàìîãî UP.

Äà Á–ã ñ íèì. ß âîâñå íå ñ÷èòàþ åãî îáðàçöîì äëÿ ïîäðàæàíèÿ è ãëóáîêèì ìûñëèòåëåì. Õîòÿ óâàæàþ.

Èíòåðåñíî, ÷òî îí ó÷àñòâîâàë â òðåõ èç ÷åòûðåõ ìîèõ ïåðâûõ êîíôåðåíöèé. Ïðè÷åì íà ïåðâûõ äâóõ îí âñòàâàë â íà÷àëå ìîåãî äîêëàäà, óõîäèë, è âîçâðàùàëñÿ ê êîíöó. À âîò íà òðåòüåé ñëóøàë, è äàæå çàäàâàë âîïðîñû. Ýòî áûëî çà ïîëãîäà äî åãî êîí÷èíû.

Ïðèâåò,

Ôðàíöóçèê.

December 2025

S M T W T F S
  123 4 56
78 9 10 11 1213
1415 1617181920
21 22 23 24 2526 27
28293031   

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Dec. 28th, 2025 07:22 pm
Powered by Dreamwidth Studios