Бактерии научились решать судоку

В информатике есть понятие клеточного автомата – это двух- или трехмерное поле ячеек, состояние каждой из которых определяется набором простых правил в зависимости от состояния соседних ячеек. Наиболее известным примером является игра "Жизнь", которая при весьма простых правилах для каждой отдельной ячейки приводит к довольно сложному поведению системы в целом и позволяет (благодаря эквивалентности машине Тьюринга) произвести выполнение любого алгоритмизуемого задания.

Японские ученые подошли к понятию клеточного автомата буквально и построили систему из взаимодействующих бактерий, которая способна находить правильные решения для судоку. "Поскольку правила судоку просты, мы подумали, что, возможно, бактерии смогут решить его, если мы заложим в них правила, которым они должны следовать", - говорит возглавивший команду Рио Таниучи (Ryo Taniuchi). Для того, чтобы заложить правила поведения каждой отдельной бактерии применялись методы генного ижиниринга, когда при помощи вирусов в организм встраиваются гены, заставляющие его определенным образом реагировать на внешние сигналы.

Поле игры представляло из себя квадрат 4×4, каждая бактерия могла принимать один из четырех возможных цветов. Каждый цвет соответствовал числу от 1 до 4. Задачей для бактерий являлось найти такую комбинацию чисел, чтобы ни в одном ряду и столбце не было повторов.

Использовались 16 типов бактерий. Каждый – с уникальной генетической меткой, номер которой соответствовал координатам на игровом поле. Каждая бактерия могла принимать один из четырех возможных цветов, соответствовавших четырем цифрам. Изначально некоторые бактерии были уже определенного цвета, что задавало исходные условия головоломки.

Бактерии, уже определившиеся со своим цветом, посылали другим бактериям сигналы (участки РНК, упакованные в вирусы), содержащие информацию о своих координатах и цвете. Бактерии были "запрограммированы" так, чтобы принимать сигналы только от бактерий, находящихся в том же ряду или столбце. Эти сигналы не позволяли бактериям принять уже занятый другими цвет, оставляя в итоге им единственный правильный вариант: такой, который исключает повторы в рядах и столбцах. Это в итоге и давало правильный вариант решения задачи.

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