Случайность и хаос - Рюэль Д.
Скачать (прямая ссылка):
сложны, чтобы мы могли на них ответить. Подумайте о музыкальных мелодиях;
это сообщения, которые, как нам кажется, мы понимаем, но при этом мы, в
общем-то, не можем сказать, что они означают. Существование музыки - это
постоянный позор для интеллекта, но он лишь один из множества других ему
подобных. Ученые знают, как сложно понять простые явления вроде кипения
или замерзания воды, поэтому они не особенно удивляются, когда
обнаруживают, что очень многие вопросы, связанные с человеческим разумом
(или функционированием мозга) в настоящее время находятся за пределами
нашего понимания.
Глава 22
СЛОЖНОСТЬ, АЛГОРИТМИЧЕСКАЯ
Наука развивается за счет создания новых концепций: новых идеализаций в
физике, новых определений в математике. Некоторые из вновь введенных
концепций через какое-то время оказываются неестественными или
непродуктивными. Другие же показывают себя более полезными и
фундаментальными, чем можно было предположить. Информация стала одной из
наиболее успешных концепций современной науки. Помимо всего прочего,
информация позволяет нам подойти к проблеме сложности.
Нас окружают сложные объекты, но что же такое сложность? Сложны живые
организмы, сложна математика, сложна конструкция космического корабля.
Что общего во всех этих вещах? Вероятно, то, что все они содержат много
информации, которую не так легко получить. Пока мы все еще не можем
создавать живые организмы с самого начала; мы мучаемся с доказательством
некоторых математических теорем, да и конструкция космических кораблей
требует от нас немало усилий.
Некоторая сущность является сложной, если она заключает в себе какую-то
информацию, которую сложно получить. Мы не сказали, что значит "сложно
получить", а потому наше определение сложности не имеет точного значения.
Фактически же наш естественный язык, которым мы пользуемся в повседневной
жизни (в данном случае, русский), позволяет нам давать замечательно
неопределенные определения, вроде приведенного выше. И это действительно
скорее благо, нежели досадная неприятность. Однако если мы хотим
заниматься наукой, то мы должны быть более точными, более формальными.
Вследствие этого мы получим не одно, а несколько определений сложности, в
зависимости от предпосылок, из которых будем исходить. Например,
серьезное исследование сложности жизни, в качестве предпосылки, должно
включать физическую вселенную, в которой эта самая жизнь
130
Глава 22
развивается. Однако существуют и такие концепции сложности, которые можно
развить с помощью чисто математических предпосылок. Сейчас я рассмотрю
именно такую концепцию, концепцию алгоритмической сложности.
Вкратце, алгоритм - это систематический способ выполнения определенного
задания. Например, всем нам знаком алгоритм умножения двух целых чисел.
Алгоритм всегда берет входное сообщение, типа "3 х 4" (записанное с
помощью символов 0,1, 2,..., 9, х) и выдает выходное сообщение, типа
"12". Безусловно, в наши дни умножение гораздо легче выполнять с помощью
компьютера, и тогда алгоритм можно определить как задачу, выполняемую
компьютером (в который заложена подходящая программа). То, что мы
подразумеваем под компьютером, фактически является несколько
идеализированной машиной, в распоряжении которой находится бесконечный
объем памяти. (Мы не желаем ограничивать определение алгоритмов только
потому, что серийные компьютеры не могут ввести в свою память число,
содержащее 1Е100 разрядов.)
Британский математик Алан Тьюринг изобрел и точно описал компьютер,
который хорошо подходит для теоретического изучения алгоритмов, хотя этот
же самый компьютер оказался бы замечательно неадекватным для их
реализации на практике. Машина Тьюринга имеет конечное число внутренних
состояний: несколько так называемых активных состояний и одно состояние
остановки.
Машина выполняет свою работу на бесконечной бумажной ленте, поделенной на
непрерывный ряд квадратов (эта лента служит памятью). На каждом квадрате
ленты записан символ конечного алфавита, причем один из символов является
пробелом. Машина Тьюринга действует в последующие моменты времени
совершенно предсказуемым образом. Если она находится в состоянии
остановки, она вообще ничего не делает. Во всех остальных случаях
дурацкая машина считывает квадрат, на котором она находится, и потом, в
зависимости от своего внутреннего состояния и от того, что она только что
считала, делает следующие вещи:
(а) она стирает то, что было написано, и записывает в квадрат что-то
еще (или то же самое);
(б) она переходит на один квадрат влево или вправо;
(в) она переходит к новому внутреннему состоянию.
Затем машина начинает другой цикл, в зависимости от того, что она
считывает в новом квадрате и каким является ее новое внутреннее
состояние.
Сложность, алгоритмическая
131
Исходное состояние ленты содержит конечное сообщение, которое является
входным (оставшаяся часть ленты пуста, т. е. состоит из квадратиков,
помеченных символом "пробел"). Машина начинает с одного конца сообщения,
