Американский математик Рэй Соломонов , в возрасте 16 лет, поставил перед собой поразительную цель – найти метод, который мог бы решить любую научную проблему. В то время как большинство подростков мечтает о более приземлённых вещах, Соломонов стремился к тому, чтобы разработать алгоритм, который смог бы объяснить все явления в мире с помощью простых закономерностей. Эта амбициозная идея привела к созданию совершенно новой области исследований, которая позволяет систематически искать закономерности в данных и выявлять скрытые процессы, определяющие устройство нашего мира.
Несмотря на то, что эти идеи могут напомнить современные методы работы искусственного интеллекта, Соломонов впервые сформулировалих еще в 1942 году, задолго до появления первых AI-алгоритмов. В основе его подхода лежал принцип бритвы Оккама, согласно которому самое простое объяснение для любого явления является, как правило, самым верным. Этот принцип активно используется физиками при поиске формул, описывающих как можно больше физических процессов с минимальной сложностью.
Соломонов стремился создать набор правил или алгоритм, который бы выявлял самые простые связи в данных. Он верил, что с его помощью можно было бы объяснить всё. Например, если записать траекторию полета брошенного бейсбольного мяча, можно предложить множество математических формул, описывающих его движение. Однако верным, скорее всего, будет простейший закон – законы Ньютона, описывающие взаимодействие силы броска и силы тяжести, действующей на мяч.
Таким образом, Соломонов хотел найти правило, которое бы позволило выбрать самое простое объяснение из всех возможных. Это правило можно было бы перевести в компьютерную программу, в которую загружались бы данные, а на выходе получалось бы простейшее объяснение этих данных. Такая программа могла бы стать настоящей “машиной чудес.”
Проблема определения “простоты”
Однако стоит отметить, что программа, способная находить самые простые объяснения, так и не была создана – и, вероятно, никогда не будет. Тем не менее, именно эти идеи подростка Соломонова стали началом нового направления в науке, которое изучает природу случайности и сложности. Как это часто бывает в естественных науках, аналогичные мысли появились и у других исследователей того времени.
Одним из таких исследователей был советский математик Андрей Колмогоров , который сосредоточился на вопросах вероятности и случайных чисел. Его интересовало, как можно определить, является ли описание какого-то явления простым или сложным.
Например, если показать вам число 25 041 903, оно может показаться случайным на первый взгляд. Есть множество способов объяснить его происхождение: оно могло быть результатом генератора случайных чисел, или же это произведение простых чисел 3, 61 и 136 841. А может быть, это число занимает определенное место в бесконечной последовательности числа Пи, или же связано с датой рождения Колмогорова – 25 апреля 1903 года. Какое из этих объяснений кажется самым простым? Для каждого человека ответ может быть разным.
Колмогоров разработал объективный метод для определения сложности объектов. Так называемая сложность Колмогорова числа определяется длиной самой короткой компьютерной программы, которая может его вычислить. Чем короче программа – тем проще число.
Однако сложность Колмогорова зависит от используемого языка программирования. Программа на Python может оказаться короче программы на C++, и наоборот. Любая компьютерная программа может быть выражена в машинном коде – последовательности нулей и единиц. Длина самой короткой последовательности нулей и единиц, которая позволяет компьютеру вычислить нужное значение, соответствует сложности Колмогорова этого числа.
Таким образом, чтобы вычислить сложность Колмогорова числа 25 041 903, можно перевести различные объяснения этого числа (например, через простые числа или позицию в числе Пи) в компьютерные программы и посчитать количество символов в соответствующем машинном коде.
Парадокс, разрушающий мечту
На первый взгляд может показаться, что мечта Соломонова воплотилась в реальность с помощью сложности Колмогорова – ведь она позволяет выявить закономерности в любых данных. Однако на пути к этому возник парадокс, который разрушил идею создания универсального алгоритма. Этот парадокс был впервые описан философом Бертраном Расселом, который в 1908 году приписал его библиотекарю Г. Г. Берри.
Пример парадокса Берри можно описать так: предположим, что у нас есть словарь из 20 слов, с помощью которых мы пытаемся описать разные числа. Мы можем начать с простых комбинаций этих слов, чтобы постепенно определять числа, как это предлагал Колмогоров с программами. Но количество комбинаций ограничено, а чисел – бесконечно много. В итоге мы столкнемся с числом, которое не может быть описано с помощью 20 слов. Но что, если описать это число как “наименьшее число, которое не может быть описано 20 словами или менее”? В таком случае определение этого числа состоит всего из 12 слов, что создает противоречие.
Парадокс Берри показывает, что невозможно определить, сколько слов (или символов программы) нужно для описания числа. Это связано с тем, что математика неполна – некоторые истины в ней просто не могут быть доказаны.
Предположим, что существует программа K, которая вычисляет сложность Колмогорова для любого числа. Допустим, программа состоит из миллиона символов. Мы можем ввести в программу все возможные числа, пока не найдем большое число x, сложность которого равна двум миллионам символов. Теперь можно создать новую программу P, которая будет проходить все возможные строки и использовать программу K для вычисления сложности этих строк, пока не найдет строку с длиной в два миллиона символов. Программа P, зависимая от программы K, будет содержать меньше двух миллионов символов, что создаст противоречие – программа с меньшей длиной вычислит число с большей сложностью.
Таким образом, мы приходим к выводу, что программа K, которая вычисляет сложность Колмогорова для любого входного значения, не может существовать.
Несмотря на всё, мечта продолжает жить
Хотя мечта Соломонова создать универсальный алгоритм для решения всех задач оказалась неосуществимой, его идеи продолжают находить применение. В большинстве случаев не требуется точное вычисление сложности Колмогорова – достаточно приближённых методов. Одним из таких методов является использование программ сжатия данных, таких как gzip. Например, если нужно узнать, связаны ли две числовые последовательности, можно сжать их по отдельности и вместе. Если сжатие объединенной последовательности почти не отличается от сжатия каждой из них, это может указывать на наличие корреляции между ними.
Сложность Колмогорова также может помочь определить случайность числовой последовательности. Например, три восьмизначных числа – 25 041 903, 47 395 929 и 10 101 010 – могли быть сгенерированы генератором случайных чисел, но каждое из них имеет свою особенность: одно число представляет дату, другое имеет явный повторяющийся паттерн. В таких случаях можно оценить, насколько эти числа соответствуют определенным закономерностям, чтобы проверить надежность генератора случайных чисел.
Таким образом, даже если сложность Колмогорова не может ответить на все загадки вселенной, идеи Соломонова и Колмогорова продолжают оказывать влияние на математику и информатику, помогая решать множество сложных задач, хотя и не универсальным способом, о котором мечтал Соломонов.