Актуальное интервью Компьютер в пробирке

Современные вычислительные машины, хотя и обладают большой мощностью, не способны решить некоторые задачи. О том, как молекулы работают там, где не справляется электроника, и почему будущее компьютеров связано с ДНК, рассказал доктор физико-математических наук, профессор Игорь Юрьевич ПОПОВ.

– Для чего был придуман ДНК-компьютер?

– Обычный компьютер, начиная с момента его изобретения, последовательно выполняет операции, по сути повторяя машину Алана Тьюринга. Конечно, произошел огромный технический прогресс, однако он не затронул принципиально новые процессы. Существуют NP-полные задачи, сводящиеся к перебору и требующие экспоненциального количества операций 2n. Обычные ЭВМ с этим просто не справятся. Так появилась идея использовать молекулы ДНК. Сами по себе они не дадут экспоненциального ускорения, но по крайней мере их много. Если мы будем использовать, допустим, один моль молекул (1023), то получим параллельное выполнение 1023 операций. Эффект будет такой, словно в компьютере стоит процессор на 1023 ядер.

– Как работает подобный механизм?

– Молекула ДНК состоит из двух цепочек, которые сцепляются друг с другом по строго заданному правилу. В каждой цепочке есть четыре типа оснований, которые могут соединяться только попарно: аденин – тимин, гуанин – цитозин. Эту комплементарность нужно использовать. Мы можем разрезать ДНК ферментами и склеивать определенным образом. Однако количество операций, реализуемых биохимиками, ограничено. Поэтому возможности для построения алгоритма небольшие. К тому же для их использования нужно придумать, как кодировать информацию в молекулах, как с ней работать и получать результат. Последнее обычно просто – вынуть ДНК и расшифровать. А вот первые две операции сложные и связаны друг с другом, потому что способ кодировки зависит от используемого алгоритма, который можно осуществить переливанием из пробирки в пробирку, нагреванием и охлаждением молекул.

– Какие алгоритмы уже существуют?

– ДНК-алгоритмов в мире придумано совсем немного, около двух десятков. Наш первый алгоритм мы создали несколько лет назад, он касался составления расписаний. Это сложная задача, и компьютерных программ, которые хорошо с ней справляются, пока нет. Необходимо осуществить перебор с большим количеством субъектов: предметами, студентами, преподавателями и аудиториями.

Сейчас это теоретический проект. Вся его структура прописана, но не реализована в пробирочном варианте из-за трудоемкости процесса. Я не уверен, что наши диспетчеры будут переливать ДНК, чтобы узнать, кого в какую аудиторию направить. Однако в любом случае молекулы справились бы с этим быстрее человека.

Мы занимаемся разработкой алгоритма решения задач, ответ на которые получают, задавая вопросы с вариантами «да» или «нет». Если структурировать набор действий и расположить вопросы в нужном порядке, правильное решение гарантировано.

– Используются ли для вычислений другие молекулы?

– Один из наших студентов – Дима Никифоров (гр.6742) – придумал алгоритм составления расписаний на основе мембранных вычислений. Этот проект не связан с ДНК. Поясню на примере: нужно умножить пять на три. На результат – число, которое меньше ста и больше единицы – ставим ограничения (мембраны). Учитывая условие, что ответ должен делиться на три, возникает еще одна мембрана. И так до тех пор, пока не будет найдено искомое число. В этом случае задача будет решена без вычислительных действий, только при помощи выделения неких правил.

Алгоритм можно реализовать на молекулярном уровне с реальными мембранами, благодаря их избирательности. Конечно, проводить такие вычисления, для того чтобы посчитать простые арифметические примеры, никто не будет. Это имеет смысл, когда задача, опять же NP-полная, сводится к перебору, так как мембрана может фильтровать большой массив веществ.

– Как будут использоваться подобные алгоритмы в будущем?

– Пока мы занимаемся тем, чего не существует, однако математику обычный компьютер уже не интересен. Возможно ДНК-компьютеры никогда не будут созданы, но наши алгоритмы останутся и будут реализованы. А способ мы обязательно найдем.