Полет глайдера

Биоразнообразие Самое известное изобретение Конвея — это придуманная им в 1969 году игра «Жизнь» . Строго говоря, идею самореплицирующихся систем обдумывали еще в 1940-е годы Джон фон Нейман и Станислав Улам. В частности, фон Нейман, создавая такую самовоспроизводящуюся машину, пришел к идее клеточных автоматов — дискретной среды, где состояние ячеек меняется по определенным правилам. Опираясь на эту среду, он смог создать «универсальный конструктор» — машину, которая может бесконечно воспроизводить сама себя. Но клеточные автоматы фон Неймана были крайне сложны — у них было несколько десятков возможных состояний, которые кодировались разными цветами. Конвей радикально упростил законы, по которым работает клеточный автомат, и с этого момента начался расцвет этой области математики и компьютерной науки. Придуманная им игра «Жизнь» устроена так: на бесконечной бумаге в клеточку часть клеток объявляется «живыми» (или заполненными, их обычно закрашивают), а остальные «мёртвыми» (или пустыми). После этого их конфигурация начинает вся одновременно эволюционировать по исключительно простым правилам: Можно сказать, что «Жизнь» оказалась «живой»: всего лишь два простых правила породили множество разных «существ» с разным поведением. Вот некоторые из них. Квадрат 2 × 2 («блок») так и остаётся неподвижным: у каждой его клетки по три соседа. Прямоугольник 2 × 3 делает за всю свою жизнь одно движение — за один ход становится «ульем», и больше уже не меняется никогда. Кроме статичных форм в «Жизни» найдено множество осцилляторов, форм, через определенный период возвращающихся к прежней конфигурации. Самая простая из них: линия из трех клеток, которая за ход поворачивается на 90 градусов вокруг центра («семафор»). Сейчас известно около сотни разных типов осцилляторов, в том числе исключительно сложных, состоящих из нескольких тысяч ячеек . Глайдер (или планер) — конфигурация, которая движется с постоянной скоростью под углом в 45 градусов. Сейчас такие движущиеся конфигурации объединяют в класс «космических кораблей», среди них есть те, что движутся по диагонали, есть и те, что перемещаются по вертикали или горизонтали. После открытия глайдера Конвей, глядя на еще одну фигуру — r-пентамино (эта фигура живет долгой и бурной жизнью, исследователи мира «Жизни» относят его к классу «мафусаилов») — предположил, что бесконечно растущие конфигурации в жизни невозможны. И объявил приз в 50 долларов тому, кто это предположение опровергнет. Приз получил Билл Госпер, придумавший глайдерное ружье, фигуру, постоянно «стреляющую» глайдерами. Позже сам Конвей говорил, что он хотел получить опровержение. Это означало бы, что исключительно простая по своим правилам «машина» способна порождать исключительно сложные вещи. Сейчас глайдерных ружей — строго периодических и с колеблющимся периодом — известно как минимум несколько десятков. Буквально через пару недель после создания глайдерного ружья и благодаря ему было доказано, что «Жизнь» Тьюринг-полна: то есть любую программу, которую можно запустить на каком-нибудь компьютере, можно эмулировать с помощью «Жизни». Можно даже запустить «Жизнь» на «Жизни» — и да, продолжать эту цепочку дальше. Структуры, похожие на мгновенные снимки клеточные автоматов в работе, ученые находят в живой природе — например, узор на чешуе глазчатых ящериц строится по принципу дискретной модели клеточного автомата фон Неймана: цвет чешуйки зависит от цвета «соседей». Еще один пример — узор раковин моллюсков . Квантовая свобода Результат, значительно менее известный чем «Жизнь», но который высоко ценил сам Конвей — это теорема о свободе воли ( Free Will Theorem ), доказанная им совместно с Саймоном Коченом (Simon Kochen). Эта теорема, доказательство которой основано на мысленном эксперименте, имеет отношение не столько к философскому понятию «свободы воли», сколько к квантовой механике. Еще основатели квантовой теории спорили, действительно ли события в квантовом мире абсолютно случайны, и не могут быть предсказаны точно, а только с определенной вероятностью. Чтобы обойти эту проблему, была предложена гипотеза «скрытых параметров» — мы не можем их фиксировать, но им подчиняются случайные с нашей точки события. Именно в защиту этого предположения Эйнштейн сказал знаменитое «Бог не играет в кости». Теорема Конвея показывает, что поведение квантовомеханических объектов не может быть детерминировано никакими скрытыми закономерностями, никакими скрытыми параметрами. Конвей и Кочен поставили такой мысленный эксперимент. Пусть есть два достаточно удаленных друг от друга экспериментатора. Рядом с каждым из них находится одна из двух определенным образом квантово-запутанных частиц-бозонов. Суммарный спин обеих частиц равен нулю, а квадрат проекции спина на тройку пространственных осей равен 1, то есть результат измерения квадратов этих проекций для каждой частицы будет равен 1, 1, 0 или 1, 0, 1 или 0, 1, 1. Экспериментаторы одновременно нажимают одну из кнопок на приборе, выбирая, как именно измерить спин своей частицы, а именно — в проекции на какой из возможных наборов из трех перпендикулярных осей. Предположим, что экспериментаторы могут выбрать, на какие кнопки нажать, и их выбор никак не предопределен прошлым («свобода воли»), и не влияет на наблюдения другого. Из двух экспериментаторов выделим одного назовем его А. Когда А измеряет квадраты проекций, он получает тройку чисел, которая должна была бы быть 1, 1, 0, какую бы ортогональную тройку осей он не выбрал. Но если мы посмотрим на те 40 троек направлений, которые есть на рисунке выше, то увидим, что нельзя каждому из них сопоставить число 0 или 1 так, чтобы любая тройка давала бы 1, 1, 0. Этот запрет еще ничего не меняет, потому что сторонник гипотезы скрытых параметров может сказать: «А вдруг результат зависит от того, какую тройку вы будете измерять? Что тройка (x,y,z) по оси x даст не то же самое, что (x, повернутый y, повернутый z), даже если ось x совпадает?» И тут приходит на помощь экспериментатор B. Заставим его для простоты измерять только одну ось. Из-за того, что его ось имеет шанс совпасть с любой из осей, с которыми работает А, мы выясняем, что если бы была детерминированность — результат по каждой оси действительно зависел бы только от оси, а не от выбора тройки. То есть экспериментатор В выступает внешним контролером, запрещающим ситуацию «у нас все определяется тройкой, а не только одной осью» самим фактом своего существования (и своей случайности/свободы воли). Поэтому это приводит к тому, что результат измерений А должен определяться осью — а это уже, вкупе с 1, 1, 0-правилом, запрещено геометрией. Тогда поведение наблюдаемых ими элементарных частиц тоже не является (и не может являться) детерминированным — иначе невозможно обеспечить выполнение того, какими свойствами должны обладать их проекции спинов. Можно сказать, что «свободой воли» (поведение не определяется прошлым) обладают и элементарные частицы. Три группы Большая область в математике занимается исследованием групп — множеств, элементы которых можно «умножать» так, что это умножение удовлетворяет естественным аксиомам. В группе есть единица, и 1 · a = a · 1 = a, произведение не зависит от расстановки скобок — (ab)c = a(bc) — и для любого элемента a есть обратный a −1 , для которого a · a −1 = a −1 · a = 1. Естественно пытаться понять конечные группы, «разбирая» их на кусочки; формально — находя нормальные подгруппы и факторизуя по ним. Группы, которые так дальше «разбить» нельзя, называют простыми. И для групп существует аналог основной теоремы арифметики (об однозначности разложения на простые множители) — теорема Жордана—Гёльдера. Впрочем, в отличие от обычных чисел — даже если набор «кусочков» известен, из них могут «собираться» разные большие группы (даже если кусочки брать в одном и том же порядке!). Тем не менее, «для начала» нужно понять, как могут быть устроены простые конечные группы. И уже эта задача потребовала многих десятилетий для своего решения. Если конечная простая группа коммутативна — если в ней всегда выполняется тождество ab = ba — то это группа остатков по простому модулю p, где в качестве умножения выступает сложение — или, как её ещё можно описать, группа вращений правильного p-угольника (где остатку k сопоставляется поворот на (k/p) · 360°). Однако простых конечных групп гораздо больше; так, первая (по количеству элементов) некоммутативная простая группа — группа вращений правильного додекаэдра. Кстати, ещё на неё можно смотреть как на группу чётных перестановок пяти элементов — пяти вписанных в додекаэдр кубов. К счастью, многие простые конечные группы идут «понятными сериями» (например, таковы все группы чётных перестановок n ≥ 5 элементов). И остаются спорадические группы — и нахождение их всех (а главное, доказательство, что ничего при этом не пропущено) и было исключительно трудной задачей. Три из таких групп (а всего их 26) открыл Конвей; в его честь они так и называются, группы Конвея, и обозначаются Co1, Co2, Co3. Сюрреальные числа Так же, как и «Жизнь», сочетает простоту определения и глубину и другая тема, введенная Конвеем — сюрреальные числа. Их определение похоже на определение дедекиндовых сечений, определяющих вещественные числа как зазоры между рациональными. Каждое такое число задаётся тем, какие числа его точно больше, а какие точно меньше. Само число при этом окажется «самым простым» числом между этими двумя наборами. Как и в теории множеств, начать можно буквально с пустоты — {|}, самое простое число из всех, окажется нулем. Такие записи можно сравнивать, причём знать ничего для этого не надо: {0|}>0 просто потому, что это задано в определении; с другой стороны, можно и заметить, что раз {0|} > 0 > {|0}, то {0|}>{|0} (эти два числа оказываются +1 и -1). Для сложения потребуется заметить, что если x>a и y>b, то x+y>a+y и x+y>x+b. Вытекающее отсюда определение обеспечит, что x+{|} действительно x, а 1+1={0|}+{0|} = {0+1,1+0|} = {1|}. Если написать аккуратные определения и много доказательств по индукции, то окажется, что так можно построить арифметику на привычных нам вещественных числах, на ординалах из теории множеств, и много ещё на чём… Более того, хотя {0|0} явно не может описывать никакое число — ведь оно было бы и положительным и отрицательным одновременно — к нему все равно можно применить формальное определение сложения! Так можно получить описание выигрышных стратегий в игре Ним. За кадром За пределами этого рассказа осталось еще очень многое: полином Конвея в топологии — инвариант узла, позволяющий доказывать, что какие-то узлы нельзя развязать; оператор чтения ( последовательность «Посмотри-и-скажи» ); числовые фризы, которым была посвящена статья Конвея в «Кванте» в 1991 году, и вокруг которых происходит много интересного даже сегодня; сразу ставшие бестселлерами книги «On Numbers and Games» , (в соавторстве с Берлекемпом и Ги) «Winning Ways for your Mathematical Plays» , и переведенная на русский «Квадратичные формы, данные нам в ощущениях», Атлас конечных групп, в создании которого Конвей участвовал, сформулированная им и Нортоном гипотеза Monstrous Moonshine, относящаяся к самой большой спорадической простой группе, Монстру — и ещё многое. Но хочется завершить этот текст словами Мартина Гарднера о формуле Конвея для вероятности выигрыша в игру Пенни : «Я не понимаю, почему это работает. Она просто выдаёт ответ как по волшебству, как многие другие алгоритмы Конвея». Виктор Клепцын, Михаил Раскин