Во что играл британский математик Джон Конвей
Джон Конвей говорил, что не проработал ни единого дня, а только играл. Но эти игры оказались невероятно захватывающими для его коллег и учеников. Чтобы рассказать обо всем, что сделал математик, потребуются тысячи страниц, целую книгу можно написать только о придуманном Конвеем варианте клеточного автомата — игре «Жизнь». О том, с чем «играл» Конвей и каким запомнился коллегам, для N + 1 рассказывают математики Виктор Клепцын и Михаил Раскин.
Самое известное изобретение Конвея — это придуманная им в 1969 году игра «Жизнь».
Строго говоря, идею самореплицирующихся систем обдумывали еще в 1940-е годы Джон фон Нейман и Станислав Улам. В частности, фон Нейман, создавая такую самовоспроизводящуюся машину, пришел к идее клеточных автоматов — дискретной среды, где состояние ячеек меняется по определенным правилам. Опираясь на эту среду, он смог создать «универсальный конструктор» — машину, которая может бесконечно воспроизводить сама себя. Но клеточные автоматы фон Неймана были крайне сложны — у них было несколько десятков возможных состояний, которые кодировались разными цветами.
Конвей радикально упростил законы, по которым работает клеточный автомат, и с этого момента начался расцвет этой области математики и компьютерной науки.
Придуманная им игра «Жизнь» устроена так: на бесконечной бумаге в клеточку часть клеток объявляется «живыми» (или заполненными, их обычно закрашивают), а остальные «мёртвыми» (или пустыми). После этого их конфигурация начинает вся одновременно эволюционировать по исключительно простым правилам:
1. Если у живой клетки есть два или три живых «соседа», то на следующий ход она выживает. Во всех остальных случаях она умирает: или от «одиночества» (соседей < 2) или от «перенаселения» (соседей > 3).
2. Если у мёртвой клетки ровно три живых соседа — то на следующем ходу она становится живой.
Можно сказать, что «Жизнь» оказалась «живой»: всего лишь два простых правила породили множество разных «существ» с разным поведением. Вот некоторые из них.
Квадрат 2 × 2 («блок») так и остаётся неподвижным: у каждой его клетки по три соседа. Прямоугольник 2 × 3 делает за всю свою жизнь одно движение — за один ход становится «ульем», и больше уже не меняется никогда.
Кроме статичных форм в «Жизни» найдено множество осцилляторов, форм, через определенный период возвращающихся к прежней конфигурации. Самая простая из них: линия из трех клеток, которая за ход поворачивается на 90 градусов вокруг центра («семафор»). Сейчас известно около сотни разных типов осцилляторов, в том числе исключительно сложных, состоящих из нескольких тысяч ячеек.
Глайдер (или планер) — конфигурация, которая движется с постоянной скоростью под углом в 45 градусов. Сейчас такие движущиеся конфигурации объединяют в класс «космических кораблей», среди них есть те, что движутся по диагонали, есть и те, что перемещаются по вертикали или горизонтали.
После открытия глайдера Конвей, глядя на еще одну фигуру — r-пентамино (эта фигура живет долгой и бурной жизнью, исследователи мира «Жизни» относят его к классу «мафусаилов») — предположил, что бесконечно растущие конфигурации в жизни невозможны. И объявил приз в 50 долларов тому, кто это предположение опровергнет.
Приз получил Билл Госпер, придумавший глайдерное ружье, фигуру, постоянно «стреляющую» глайдерами. Позже сам Конвей говорил, что он хотел получить опровержение. Это означало бы, что исключительно простая по своим правилам «машина» способна порождать исключительно сложные вещи. Сейчас глайдерных ружей — строго периодических и с колеблющимся периодом — известно как минимум несколько десятков.
Буквально через пару недель после создания глайдерного ружья и благодаря ему было доказано, что «Жизнь» Тьюринг-полна: то есть любую программу, которую можно запустить на каком-нибудь компьютере, можно эмулировать с помощью «Жизни». Можно даже запустить «Жизнь» на «Жизни» — и да, продолжать эту цепочку дальше.
Структуры, похожие на мгновенные снимки клеточные автоматов в работе, ученые находят в живой природе — например, узор на чешуе глазчатых ящериц строится по принципу дискретной модели клеточного автомата фон Неймана: цвет чешуйки зависит от цвета «соседей». Еще один пример — узор раковин моллюсков.
Результат, значительно менее известный чем «Жизнь», но который высоко ценил сам Конвей — это теорема о свободе воли (Free Will Theorem), доказанная им совместно с Саймоном Коченом (Simon Kochen). Эта теорема, доказательство которой основано на мысленном эксперименте, имеет отношение не столько к философскому понятию свободы воли, сколько к квантовой механике.
Еще основатели квантовой теории спорили, действительно ли события в квантовом мире абсолютно случайны, и не могут быть предсказаны точно, а только с определенной вероятностью. Чтобы обойти эту проблему, была предложена гипотеза «скрытых параметров» — мы не можем их фиксировать, но им подчиняются случайные с нашей точки события. Именно в защиту этого предположения Эйнштейн сказал знаменитое «Бог не играет в кости».
Теорема Конвея показывает, что поведение квантовомеханических объектов не может быть детерминировано никакими скрытыми закономерностями, никакими скрытыми локальными параметрами.
Конвей и Кочен поставили такой мысленный эксперимент. Пусть есть два достаточно удаленных друг от друга экспериментатора. Рядом с каждым из них находится одна из двух определенным образом квантово-запутанных частиц-бозонов. Эти частицы имеют спин 1, и они запутаны так, что их суммарный спин равен нулю. Сумма квадратов проекции спина на тройку перпендикулярных пространственных осей равна спину частицы, то есть 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. Заставим его для простоты измерять только одну ось. Если эта ось совпадет с одной из осей, выбранных A, квадрат проекции окажется одинаков из-за противоположности спинов (этот на первый взгляд естественный факт на самом деле связан с тем, что способ и порядок измерений не важны). Из-за того, что его ось имеет шанс совпасть с любой из осей, с которыми работает А, мы выясняем, что если бы была детерминированность — результат по каждой оси действительно зависел бы только от оси, а не от выбора тройки.
То есть экспериментатор В выступает внешним контролером, запрещающим ситуацию «у нас все определяется тройкой, а не только одной осью» самим фактом своего существования (и своей случайности/свободы воли). Поэтому это приводит к тому, что результат измерений А должен определяться осью — а это уже, вкупе с 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, относящаяся к самой большой спорадической простой группе, Монстру — и ещё многое. Но хочется завершить этот текст словами Мартина Гарднера о формуле Конвея для вероятности выигрыша в игру Пенни:
«Я не понимаю, почему это работает. Она просто выдаёт ответ как по волшебству, как многие другие алгоритмы Конвея».
Виктор Клепцын, Михаил Раскин