Пиксель. История одной точки

Что произойдет, если количество шагов в алгоритме станет невероятно огромным, число циклов многократно увеличится, уровень их вложенности значительно углубится, а условные переходы сильно разветвятся? Задавая такие вопросы о систематических процессах на рубеже XX века, математики проложили путь к миру универсальных вычислительных машин, хотя сами и не догадывались об этом. Они еще не осознали двойного великолепия Гибкости и Усиления, а также присущих им сверхспособностей.

е-Проблема

Давид Гильберт, король математиков, работал в Геттингенском университете — центре математической вселенной, пока в 1930-е годы нацисты не подвергли гонениям профессоров еврейского происхождения. Еще в 1900 году он использовал свой международный авторитет, чтобы привлечь внимание к проблемам, затрагивающим основы математики. Наибольшую известность из них получили Вторая (противоречивы или нет аксиомы арифметики?) и Десятая (Есть ли универсальный алгоритм решения диофантовых уравнений?). Каждый, кто сумеет решить любую из них, сразу же будет признан математиком мирового уровня.

В 1928 году Гильберт сформулировал еще одну проблему. Она связана с простой логической системой, именуемой логикой первого порядка. Математики прибегают к ней, чтобы независимо от используемого языка точно формулировать утверждения, которые могут быть истинными или ложными. Гильберт задался вопросом, существует ли систематический способ, алгоритм, позволяющий определить истинность или ложность утверждения в этой простой логической системе.

Возьмем утверждение: все предметы — сосновые шишки. Или вот еще одно: все предметы — это айва. Если объединить два этих утверждения союзом или, получится составное утверждение, которое всегда разрешено в такой системе: все предметы — сосновые шишки, или все предметы — айва. В системе есть правило, позволяющее заменить составное утверждение эквивалентным: все объекты — сосновые шишки или айва. Здесь слово «эквивалентный» означает, что если первое утверждение верно, то верно и второе, а если первое ложно, то ложно и второе. Таким образом, перестановка слов не меняет истинности утверждения. Простая перестановка сводит два начальных утверждения, объединенных союзом или, в одно, при этом или занимает положение между сосновыми шишками и айвой, а не между двумя утверждениями. Может показаться очевидным, но суть в том, что каждый шаг в этой логической системе преобразует одно утверждение в эквивалентное с помощью простой, даже тривиальной операции. Новое утверждение вытекает из старого.

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

Математиков интересуют именно истинные утверждения. Ученые начинают с очень простых — заведомо истинных — утверждений и выводят из них при помощи логической системы более сложные. Исходные истинные утверждения называют аксиомами. Например, утверждение, что число равно самому себе, — это аксиома. Очевидно, оно всегда верно. Впечатляющая сила математики заключается в том, что такие выводы могут привести к совершенно неожиданным результатам, хотя каждый шаг прост и очевиден.

Поставленная Гильбертом задача предполагала поиски алгоритма решения, а не самого вывода. Он не требовал, чтобы в результате систематического процесса действительно из аксиом выводилось утверждение, а требовал, чтобы точно определялась возможность или невозможность вывода. Различие кажется несущественным. Если вы можете определить истинность утверждения, зачем показывать, как оно получено из аксиом? Однако это принципиально важно.

Сегодня научная генеалогия позволяет узнать, что, скажем, Джозеф, живший в XVIII веке, был прямым предком ныне живущего Якова; формально отслеживать родственные связи от отца к сыну — поколение за поколением — при этом не требуется. Если у них одинаковые ДНК на Y-хромосоме (мужской), что легко подтверждается простым лабораторным тестом, значит, они связаны по мужской линии. Путь между ними должен существовать. Но знание о его существовании совсем не похоже на конкретный перечень мужчин, передавших конкретную ДНК своему потомку, то есть на то, что довольно трудно установить документально. Однако наличие такого знания может побудить вас приложить усилия для поиска фактического пути, ведь вы будете уверены, что не потратите время впустую.