Изменчивая природа математического доказательства. Доказать нельзя поверить

По мере того как становились обыденными доказательства тождеств все более широких классов и даже теорем других видов, мы стали наблюдать много результатов, для которых знаем, как построить доказательство (или опровержение); но не можем или не хотим платить за такое построение, так как «почти уверенность» можем приобрести гораздо дешевле. Я даже могу вообразить аннотацию статьи в 2100 г.: «В определенном точном смысле мы показываем, что гипотеза Гольдбаха верна с вероятностью более 0,99999 и что ее полное доказательство требует бюджета в $10 млрд».

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

— Дорон Зельбергер

7.1 Краткая история вычислителей

Первыми вычислительными орудиями были счетные доски. Самые примитивные из них, известные с 1200 до н. э., представляли собой доску или каменную скрижаль, покрытую слоем песка, на котором можно было делать пометки. Позднее на счетных досках появились бороздки или металлические диски, которые можно было использовать, чтобы отмечать позицию. Самая старая дошедшая до нас счетная доска — это таблица, найденная на острове Саламис около 300 до н. э. (см. рис. 7.1).

Первой счетной машиной был абак. Принято приписывать его изобретение китайцам. Впервые (насколько это известно) о нем упоминается в книге восточной династии Хан, написанной Ху Ю в 190 г. Это рамка, обычно деревянная, с прутиками, вдоль которых могут скользить бусины (см. рис. 7.2). В современных абаках каждая бусина в нижней части абака означает единицу, а бусина в верхней — пять.

В Древней Греции и Древнем Риме были распространены счетные доски. Абак развивался медленно, более 1000 лет. Современный абак получил популярность в Китае во время династии Сонг в 960–1127 гг. Позднее использование абака распространилось в Японии и Корее. Его можно встретить и в наше время. В Тайване и Китае не редкость увидеть кассира, проверяющего точность электронной кассы на абаке!

 

Рис. 7.1. Таблица с острова Саламис 

 

Рис. 7.2. Абак 

 

Рис. 7.3. Передача Паскаля

Первый механический вычислитель был придуман Блезом Паскалем (1623–1662), математиком, знаменитым своими работами по теории вероятностей и философскими сомнениями. Паскаль построил свою машину в 1642 г., вдохновленный конструкцией Герона Александрийского (10–70 гг.). Паскаль хотел отмерять расстояние, пройденное каретой.

Его идея до сих пор используется в счетчиках воды и автомобильных одометрах. Ее основа — однозубцовая передача, зацепленная с многозубцовой (рис. 7.3). Однозубцовая передача должна быть достаточно велика, чтобы сцепляться с многозубцовой только после того, как карета проедет единицу расстояния. Никто иной как Готфрид Вильгельм фон Лейбниц (1646–1716) доработал вычислитель Паскаля так, что тот стал умножать. Для такой машинки умножение заключалось в последовательном многократном сложении. Возможно, что изобретением Паскаля была спровоцирована технофобия, так как в то время даже математики боялись, что новая машинка подорвет их карьеру.

Первый настоящий механический вычислитель был изобретен Томасом Кольмаром (1785–1870) в 1820 г. Он умел складывать, вычитать, умножать и делить. Чарльз Бэббидж (1791–1871) воспользовался идеей Кольмара, дополнив ее собственными. Еще в 1812 г. Бэббидж понял, что многие длинные вычисления включали в себя повторяющиеся шаги. Он рассудил, что можно построить вычислительную машину, которая возьмет на себя автоматическое выполнение этих шагов. Прототип своей «разностной машины» он построил в 1822 г. А вскоре после этого получил от британского правительства субсидию для развития своей идеи. Однако в 1933 г. Бэббиджу в голову пришла идея получше.