Принципиально новый компьютер уже возможен

Принципиально новый компьютер уже возможен

Биологам удалось собрать на основе бактерий вычислительное устройство, которое может стать основой для принципиально новых компьютеров в будущем.
Исследователям из нескольких научных центров США удалось использовать генетически модифицированные бактерии кишечной палочки для решения задачи о перемещении между несколькими точками. О том, что решение найдено, «компьютер» из живых клеток сообщал, флуоресцируя желтым светом.

Графы и циклы
Задача о поиске так называемого гамильтонова цикла является классической математической задачей. Путешественнику требуется проехать по нескольким деревням так, чтобы нигде не побывать больше одного раза, и при этом посетить их все. Естественно, у него есть карта дорог, по которым можно передвигаться.

Пример графа и пути, по которому можно обойти все точки, не побывав ни в одной из них дважды. Такой путь называется гамильтоновым циклом. Изображение пользователя Wikipedia — Zorgit.

Эта задача относится к разделу математики, который носит название теории графов. Граф – это произвольный набор соединенных друг с другом точек; очевидно, что в нашей задаче такими точками являются деревни, соединенные дорогами.

Теория графов имеет широкое практическое применение: от анализа пробок на дорогах до расчета скорости химических реакций и работы генов. Впрочем, американские биологи и математики подошли с противоположной стороны – вместо анализа работы генов методами теории графов они добились решения задачи теории графов при помощи генов.

Почему бактерии?
Бактерии, на первый взгляд, проигрывают компьютерам по всем параметрам. Даже если бактерию научить решать сложные задачи, то она будет делать это намного медленнее (на решение описанной выше задачи у исследователей задачи ушло около 16 часов), да и ввод-вывод данных с такого вычислительного устройства затруднителен.
Но, как поясняют ученые, против обычных компьютеров есть один существенный аргумент: сложность некоторых задач при расширении условий растет слишком быстро. Иными словами, если надо решить задачу о поиске пути через десять деревень вместо девяти – требуемое время может вырасти вовсе не на десять процентов.
Число возможных путей для N точек (то есть маршрутов, которые требуется проверить на соответствие условию задачи) считается так: 1 × 2 × 3 x … x N – для десяти точек можно найти свыше 3,6 млн вариантов. Для 11 точек речь будет идти о 40 млн, а для 12 – о полумиллиарде. 24 населенных пункта можно обойти 8841761993739701954543616000000 способами.

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

Ввод и вывод
Ученым удалось разработать метод кодирования условий задачи – они создали искусственную молекулу ДНК, каждый из участков которой соответствовал либо одной точке, либо переходу между двумя точками. Кроме того, в бактерию добавили фермент, который мог случайным образом вырезать эти фрагменты и менять их местами.

Перемешанные фрагменты сами по себе были для клетки бесполезны, но как только они собирались в правильной последовательности, то из них складывался работоспособный ген. Точнее – два гена, кодирующие красный и зеленый флуоресецентные белки. Вместе они давали желтую флуоресецнцию, которая указывала на то, что правильная последовательность собрана.

Таким образом, для ввода информации требовалось ввести в бактерии короткую молекулу ДНК с «условием задачи». Далее бактерии помещались в питательную среду, в них шел процесс перебора всех возможных вариантов (ученые оставляли микроогранизмы на ночь в специальном инкубаторе), а как только в питательной среде начинала появляться желтая флуоресценция – испускавшие свет бактерии извлекались для анализа ДНК.

Первый прототип
Ученые, изложившие свои выводы в Journal of Biological Engineering, подчеркнули, что пока речь идет только о проверке работоспособности бактериальных «компьютеров». Им или тем исследователям, которые продолжат их работу, придется еще разработать методы более быстрого ввода условий задачи и научить выдавать сообщение о достижении правильного результата там, где он заранее неизвестен (в опубликованной статье рассмотрен случай, когда верный ответ был известен заранее). Но Джордан Баумгарднер, один из автор исследования, считает что их работа уже подтвердила потенциальную мощь биологического подхода к решению математических задач.

352
Комментарии (6)
  • 31 июля 2009 в 13:59 • #
    Сергей Канторский

    Начертывается путь к аналоговым принципам работы компов и соответственно взаимосочетания аналоговых и цифровых методов кодирования информации, а сейчас традиционно в компах используют только цифровой

  • 31 июля 2009 в 14:11 • #
    Иван Купка

    может быть лучше говорить о дискретных, точечных, пиксельных и недискретных, волновых способах кодировки информации??
    цифровой как вид дискретного
    аналоговый как вид недискретного

  • 31 июля 2009 в 19:00 • #
    Сергей Канторский

    Вся живая природа построена на принципах аналоговой кодировки инфотмации, да это очень сложно для сегодняшних технологий, гораздо проще двоичный код но он требует огромных ресурсов частотных характеристик и что в дальнейшем перевесит посмотрим

  • 1 августа 2009 в 16:35 • #
    Иван Купка

    часть живой природы - мы - очень мало можем увидеть достоверной информации о всей Живой Природе
    отчасти знаем - отчасти и пророчествуем
    наши выводы об окружающем мире, как правило, охватывают очень малую часть этого мира, поэтмоу очень мало для него значат
    двоичный код - первичен, а потому будет необходимо превзойдён

  • 3 августа 2009 в 18:34 • #
    Сергей Канторский

    Всё правильно, телевизор начинали с азбуки "Морзе"

  • 4 августа 2009 в 14:18 • #
    Иван Купка

    мдя)))