Полет глайдера
Во что играл британский математик Джон Конвей
Джон Конвей говорил, что не проработал ни единого дня, а только играл. Но эти игры оказались невероятно захватывающими для его коллег и учеников. Чтобы рассказать обо всем, что сделал математик, потребуются тысячи страниц, целую книгу можно написать только о придуманном Конвеем варианте клеточного автомата — игре «Жизнь». О том, с чем «играл» Конвей и каким запомнился коллегам, для 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, относящаяся к самой большой спорадической простой группе, Монстру — и ещё многое. Но хочется завершить этот текст словами Мартина Гарднера о формуле Конвея для вероятности выигрыша в игру Пенни:
«Я не понимаю, почему это работает. Она просто выдаёт ответ как по волшебству, как многие другие алгоритмы Конвея».
Виктор Клепцын, Михаил Раскин
Почему не получились ДНК-компьютеры
Скорый кризис транзисторных процессоров в начале 1990-х казался неизбежным. И пока в одних лабораториях альтернативу искали, проектируя квантовые алгоритмы и экспериментируя с кубитами, в других — двигали компьютеры на биомолекулах. В 1994 году практически одновременно ученые собрали первый квантовый вентиль и решили первую задачу с помощью ДНК. Но к тому, чтобы двигаться дальше, одни «альтернативные айтишники» были готовы лучше, чем другие. Проектировать квантовые компьютеры начали задолго до появления кубита. Еще в 60-х теоретики занялись квантовой информатикой, а к 80-м уже думали о квантовых алгоритмах, возможном устройстве логических вентилей на кубитах, а экспериментаторы собирали разнообразные прототипы кубитов. А над теорией ДНК-вычислений никто специально не работал. Там сразу начали решать конкретные вычислительные задачи. К концу XX века биохимики научились проводить с молекулами ДНК уже довольно много процедур. Считывать с них информацию, расплетать двойную цепочку, сплетать обратно, добавлять к последовательности новые нуклеотиды, заменять один нуклеотид на другой, резать цепочку в нужном месте и сшивать. На транзисторы классических компьютеров, равно как на кубиты квантовых и их логику, вся эта биохимия непохожа. Но не видеть вычислительного потенциала в таком «натуральном» способе работы с информацией ученые не могли. Леонард Адлеман и задача коммивояжера В последовательности химических реакций можно разглядеть логическую схему. На входе одно вещество, на выходе — другое. Или несколько, но в определенном соотношении. Поэтому если правильно подобрать реакции, то строение и количество получившихся молекул может кодировать решение какой-то задачи. Первым, кто понял, что имеющихся у биологов инструментов уже хватает для вычислений, стал математик Леонард Адлеман, один из создателей системы шифрования RSA (Rivest — Shamir — Adleman). Познакомившись в начале 1990-х с миром ДНК, ученый, по его собственным словам, «отчетливо увидел» аналогию между нуклеиновой логикой и транзисторной логикой компьютерных процессоров — и уже в 1994 году опубликовал статью об эксперименте, в котором нуклеиновые кислоты решили задачу о гамильтоновом цикле на графе. Это частный случай NP-полной задачи коммивояжера (о полиномиальных и неполиномиальных задачах мы говорили в материале «Удаленное доказательство»). В задаче коммивояжера определенное количество точек на карте надо соединить самой короткой траекторией, ни одну из них при этом не пропустив. В задаче поиска гамильтонова пути надо просто доказать, что траектория, которая соединяет все точки и проходит через каждую ровно один раз, существует. Вычислитель Адлемана искал решение для графа с семью узлами. В этом ДНК-вычислителе каждому из узлов графа соответствовала случайная молекула из 20 нуклеотидов. Соответственно, ребра графа, то есть соединения узлов, складывались из двух половинок: первые десять звеньев — 3′-хвост молекулы одного узла, а вторые десять — 5′-хвост второй. Ребра таким образом становились векторами: i→j-последовательность нуклеотидов отличалась от j→i-последовательности. Это и нужно для того, чтобы синтезировать непрерывные траектории, последовательно идущие через узлы графа. Биопроцессор Адлемана использовал ДНК в качестве носителя информации, а для операций над ней — полимеразу и лигазу, которые, соответственно, синтезировали новые цепочки нуклеиновых кислот и сшивали их друг за другом. Расчеты, которые сам Адлеман в уме производил за минуту, у его компьютера заняли неделю. Это был успех — наивный эксперимент продемонстрировал принципы ДНК-вычислений. Работа стала основополагающей для всего направления «дезоксирибонуклеинового IT» и следующие несколько лет вдохновленные примером Адлемана ученые строили аналогичные ДНК-схемы для решения похожих комбинаторных задач. Оценки показывали, что если правильно спроектировать эксперимент и минимизировать потери времени на лабораторные процедуры, то для решения NP-полных задач компьютер на ДНК может оказаться эффективнее классической машины. Компьютер Адлемана проводил больше тысячи операций с производительностью 100 терафлопс — классические компьютеры достигли таких показателей только к 2005 году. Квантовые машины в те времена ничего решать не умели, так что даже компьютерами называться не могли. И ДНК-вычислители, несмотря на отсутствие теоретической базы (которая у квантовых как раз была), оказались на несколько шагов впереди. Их архитектура позволяла проводить огромное число параллельных вычислений в виде одновременных реакций молекул друг с другом. Оставалось найти под такие возможности подходящие задачи. Логические вентили Эстафету у Адлемана принял информатик-теоретик Ричард Липтон. В 1995 году он приспособил еще одну NP-полную задачу для вычисления в пробирке. В его эксперименте перед нуклеиновыми кислотами ставился вопрос о выполнимости булевых формул — нужно было доказать, что формулу, в которой есть только булевые переменные (то есть которые могут принимать значение 0 или 1), скобки и операторы И, ИЛИ и НЕ, можно выполнить. То есть найти набор значений, при которых формула оказывается верной. Эта задача отличается от задачи с графом, которую решал вычислитель Адлемана. Но Липтон не придумал ничего нового в архитектуре ДНК-процессора. Вместо инженерной задачи он решил чисто математическую — как свести задачу выполнимости к задаче на графе. Так что никаких принципиальных модификаций в оригинальный ДНК-вычислитель вносить не пришлось. Классическая машина решает задачу о выполнимости булевой формулы с n переменными, просто перебирая по очереди 2n ее вариантов на истинность. Алгоритм Липтона делает ровно то же самое, никакого процедурного ускорения в нем нет: ДНК-процессор справляется быстрее просто потому, что распараллеливает этот перебор. В 1996 году нуклеотидный процессор научили складывать двоичные числа. В 1997 — он решил задачу поиска в графе максимальной клики — то есть такого набора вершин графа, в котором все со всеми попарно соединены. В 2001 году Эхуд Шапиро, еще один классик теории программирования, запатентовал полноценную машину Тьюринга, основанную на ДНК-вычислениях с помощью ферментов. Построена она на тех же принципах, которые развивали Адлеман, Липтон и другие энтузиасты. Перспектива проводить параллельные ДНК-вычисления сразу на триллионах или даже квадриллионах молекул вселила в ученых надежду на решение NP-полных задач, слишком тяжеловесных для последовательных вычислений на классическом компьютере. Все задачи, которые к тому моменту решили нуклеиновые кислоты, брались из классической информатики. Поэтому и ставились перед нуклеотидами на языке двоичной логики — и решались, соответственно, на нем же. Хотя, как и для квантовых вычислений, двоичная система для ДНК-платформы не очень естественна: в молекулах ДНК четыре разных нуклеотида, а не два. Но полноценно возможности четверичной нуклеотидной логики в этих схемах не использовались. Если проблему перевода информации из двоичного кода в четверичный в контексте ДНК вскоре изучили довольно подробно, то вопрос о том, как из четверичных элементов строить логические вентили, оставался совсем мало проработанным. Молекулы были способом представления битов. Много молекул с нужной структурой — единица, мало — ноль. Разочарование Скептические комментарии по поводу будущего ДНК-платформ зазвучали еще в 1994 году, сразу после выхода статьи Адлемана. И во многом были справедливы. К 2000 году проблем с ДНК-процессорами накопилось достаточно много, чтобы перспективы нуклеотидных вычислителей перестали казаться радужными. Их можно разделить на четыре группы. Физические ограничения. Адлеман решил задачу поиска гамильтонова цикла на семи узлах за неделю в нескольких пробирках. Чтобы решить такую же задачу хотя бы на двух десятках узлов, по расчетам, нужны уже килограммы ДНК. А универсальному вычислителю для решения комбинаторных задач, по некоторым оценкам, нужно еще почти на 50 порядков больше олигонуклеотидов — примерно 1070 молекул. Область применения. Физические ограничения сужают и горизонт возможностей молекулярных машин: задачи, которыми изначально планировали их загружать, вероятнее всего, для них неподъемны. Так, дешифрование данных, закодированных по классическим протоколам, — задача, которую сейчас хотят решать на квантовых вычислителях, — для ДНК не под силу. На взлом 256-байтного ключа будет нужно 101233 цепочек ДНК — и компьютер объемом примерно 101216 литров. Это примерно 101199 Каспийских морей. Стало понятно, что вместо прямого переноса известных задач для нуклеиновых кислот надо искать другие. Накопление ошибок. О том, что ошибки могут заглушить всю процедуру вычислений, беспокоился еще Липтон — в своей пионерской статье он назвал их основной проблемой на пути к созданию полноценного ДНК-компьютера. Годы спустя эти вычислители так и остались очень плохо масштабируемыми. 99-процентная точность, которая для одной операции кажется более чем приемлемой, для сотни последовательных действий становится уже меньше 40 процентов. Неуниверсальность. Каждая из предложенных схем ДНК-процессора в лучшем случае была машиной Тьюринга, собранной под одну конкретную логическую задачу. В каждой есть определенный набор элементов, определенный протокол действий, они не ограничены во входной информации — и способны уверенно решать конкретную логическую задачу. Но только ее. В итоге об универсальных ДНК-компьютерах в начале 2000-х говорить перестали, а теоретики компьютерных наук постепенно переключились на другие задачи. Адлеман выпустил в XXI веке всего несколько статей про ДНК-вычисления и самосборку биомолекул в компьютерном контексте, Ричард Липтон сфокусировался на чисто математических и компьютерных исследованиях, а Эхуд Шапиро, хотя и продолжил выпускать статьи по «живой» логике, со временем переключился с ДНК на другие био-логические элементы — клетки. Параллельные ошибки Область, несмотря на общий пессимизм, не зачахла. Но фокус исследований сместился. В вычислениях на молекулах оставалось слишком много ошибок, и все еще оставалось непонятно, как их масштабировать и универсализировать. Поэтому на место математиков пришли биохимики, молекулярные биологи и биоинформатики, которые вместо того, чтобы работать над базовыми принципами логических схем ДНК-вычислителя, занялись усовершенствованием молекулярного инструментария. В частности, для решения некоторых комбинаторных задач стали активнее использовать прикрепление олигонуклеотидов к подложке. Это позволило упростить масштабирование логических схем: после логической операции нужные олигонуклеотиды остаются пришитыми к твердой поверхности и их можно использовать дальше, а лишнее просто вылить вместе с раствором. А негибридизованные одноцепочечные молекулы (то есть тоже лишние) отдать на съедение экзонуклеазам кишечной палочки. Впрочем, полностью избавиться от ошибок таким образом не удалось. Больше пяти процентов лишних цепочек оставались на поверхности после нескольких циклов очистки. Поэтому главная проблема, присущая ДНК-вычислителям, оставалась нерешенной. Другие ошибки, мутационные, также продолжали накапливаться в ходе многостадийных вычислений. Бороться с ними ученые предлагали двумя способами: либо всеми возможными способами предотвращать их, либо брать работающие с ошибками схемы и устранять в них последствия этих ошибок. Для сокращения их числа пытались подбирать оптимальную скорость реакций, управляя температурой и концентрацией реагентов, или, например, отсеивать олигонуклеотиды с ошибками. Эти варианты, впрочем, также не были универсальными, а придумывались под конкретные задачи и сильно зависели от процедуры и от платформы, на которой работает вычислитель (а к тому времени типов ДНК-процессоров было уже не меньше пяти). Исправлять мутационные ошибки предлагали либо на этапе работы с ДНК, либо при секвенировании, либо во время обработки информации уже в цифровом виде. В отдельных случаях справляться с последствиями естественных мутаций и паразитного сигнала удавалось довольно успешно, но и придумать универсальные методы так и не удалось: для каждой конкретной задачи приходилось разрабатывать свой способ устранения проблемы. В поисках более универсального и точного способа считать на ДНК биохимики стали перебирать альтернативы гибридизации, которой пользовались Адлеман и Липтон. Некоторые ученые отказались от ферментативных реакций. Сначала Милан Стоянович и Дарко Стефанович стали вместо ферментов использовать дезоксирибозимы — олигонуклетиды с функциями ферментов. Например, с помощью дезоксирибозима с функцией рибонуклеазы, способного разрезать молекулы РНК, они сделали вычислитель с 23 последовательными логическими вентилями и научили его играть в крестики-нолики на поле три на три. Замещая замещением А затем биохимики придумали логику на каскадах замещения цепи (strand displacement cascades). Эта схема основана на самосборке молекул ДНК и обратимом комплементарном связывании одноцепочечных олигонуклеотидов, и если все пройдет как надо, то пробирка с ДНК начнет светиться. Медиаторы в этой схеме — не ферменты, а другие нуклеотидные последовательности. Рабочий олигонуклеотид, который несет нужную информацию, присоединяется к вспомогательным олигонуклеотидам, которые работают вентилями. Олигонуклеотид, который попадает в систему в форме ввода, запускает каскад реакций замещения цепи между теми реагентами, уже находящиеся в системе, и передает таким образом сигнал. Конечным шагом этой цепочки реакций становится связывание одной из нуклеиновых кислот с красителем, в результате которого устройство начинает светиться. Ничего резать или копировать в такой схеме не нужно, а значит не нужны и ферменты. Оттого и дополнительные ошибки от работы ферментов в процессе вычислений не возникают. Такая платформа удовлетворяет базовым критериям архитектуры логической цепи: здесь реализованы логические функции И, ИЛИ и НЕ, они могут выполнять разветвленные и каскадные алгоритмы, имеют блочную структуру и могут восстанавливать сигнал. Это уже не однозадачная машина Тьюринга. А в 2011 году ученые еще и показали, как эту схему можно масштабировать, добавив в нее «качельные» (toehold) вентили, которые за счет обратимой реакции замещения цепи в нужный момент переносят статус «активного» с одного олигонуклеотида на другой. И если до этого начальное состояние вычислителя включало не больше 12 разных молекул ДНК, то за счет модификации это число увеличилось до 74. Таким образом удалось значительно увеличить производительность вычислителя: схема, в которой суммарно на разных стадиях было 130 разных олигонуклетодов, могла уже считать квадратные корни четырехзначных двоичных чисел. Но на фоне этих успехов число энтузиастов ДНК-вычислений продолжало неумолимо сокращаться. Никаких значительных прорывов ни в бесферментных, ни в гибридизационных вычислениях не произошло. После 2010 года цитировать классические статьи Адлемана и Липтона в научной периодике стали все меньше и меньше. Сейчас одни ученые продолжают совершенствовать качельную логику и каскадные схемы, другие вернулись к идее использования ферментов, третьи объединяют эти подходы. Например в 2019 году биохимики собрали из полимеразы и нескольких ДНК-вентилей единый арифметический элемент и частично решили проблему сборки интегральных схем. А другие научили свой процессор считать квадратные корни из 900. Но судя по количеству публикаций, от прежнего воодушевления уже ничего не осталось. Несмотря на отдельные успехи, вычислительные возможности логических элементов из ДНК так и остаются крайне ограниченными, и никаких чудес от технологии никто не ждет. Она просто продолжает тихо развиваться как независимая логическая платформа. Биологика Все вычислительные задачи для ДНК за тридцатилетнюю историю так и не вышли толком за пределы бинарификации последовательности биохимических реакций. Несмотря на обилие технических ухищрений, широкий арсенал операций и внушительную информационную емкость носителя, логика задач, предлагаемых нуклеиновым кислотам, сводилась к двоичной, а сигнал — к бинарному выводу, много ли в итоговой смеси нужных молекул (1) или мало (0). Квантовые компьютеры благодаря суперпозиции не только расширили возможности двоичной логики просто за счет того, что не нужно перебирать огромное число вариантов, а еще и предложили принципиально новые алгоритмы. С ДНК ученые фактически просто ускорили этот перебор за счет параллельных вычислений. Помимо этого, квантовые процессоры используют не только для того, чтобы сконструировать универсальный вычислитель. Сегодня они в первую очередь занимаются тем, что транзисторам дается с трудом: например моделированием квантовых систем и решением оптимизационных задач. Аналогичную нишу искали и для ДНК-процессоров. Логика ДНК строится на химических реакциях, поэтому и применять ее логично не где-то для алгебраических вычислений, а где-то в области химии. А с учетом того, что базовая вычислительная логика молекулам ДНК тоже уже доступна, можно использовать их как промежуточное звено между цифровым интерфейсом и молекулами-участниками химической реакции и управлять таким образом молекулярными машинами и нанороботам. Например, с помощью той же самой схемы каскадного замещения биохимики научились управлять белковыми нанороботами. На выходе в ДНК-логической цепи получаются аптамеры, небольшие олигонуклеотидные молекулы, которые связываются с целевыми белками и управляют ими. Из небольших олигонуклеотидных молекул делают программируемые химические контроллеры, «ДНК-роботов» используют для сортировки молекул, для управления роем микротрубочек или биороботами. Когда в 90-е годы «информатики-теоретики» в предвкушении кризиса полупроводниковых компьютеров стали искать новые платформы для вычислений, они решали свои, вполне конкретные, проблемы, а не придумывали задачу для нового инструмента. Реальность же оказалась немного иной. Современные квантовые компьютеры, которые удается интегрировать с классическими, конечно, помогают и в вычислениях. С задачами оптимизации квантовые компьютеры справляются увереннее классических (подробнее об этом читайте в тексте «Разминка для кубита»). И пользу от квантовых компьютеров извлекают физики, а не информатики, — моделируя на них квантовые системы. Решение вычислительных задач на биомолекулярных компьютерах выглядит еще более неуклюжим, чем на квантовых. И их будущее — скорее за молекулярными роботами и системами биохимического контроля. За биомолекулярным превосходством тоже охотятся, но уже на более высоком уровне. Например, в синтетической биологии в качестве вычислительных элементов биомолекулярных компьютеров предлагают использовать искусственные клетки, а возможность на них решать более сложные задачи называют «клеточным превосходством». Это значительно более сложные системы: на молекулы ДНК здесь ложится информационная нагрузка, а за логику отвечают клетки. Но и они нужны далеко не за тем, чтобы что-то считать. Собрать из нуклеиновых кислот суперкомпьютер мы не смогли. Зато научились использовать то, что они совершенно точно делают очень хорошо. Возможно и впредь, вместо того, чтобы переучивать кого-то, стоит внимательнее изучить их возможности — и потребности.