0 |
Коллектив профессора Росса Кинга (Ross D King) из Манчестерского университета (Великобритания) впервые продемонстрировал возможность реализации недетерминированной универсальной машины Тьюринга (Nondeterministic Universal Turing Machine, NUTM). Их исследование было опубликовано в Journal of the Royal Society Interface.
Теоретические преимущества такой машины, включая экспоненциальное увеличение быстродействия по отношению к электронным или квантовым компьютерам, хорошо известны уже многие годы, манчестерская же команда, с помощью компьютерного моделирования и экспериментов «в пробирке», показала, что NUTM можно создать физически, используя молекулы ДНК, основания аденин, гуанин, цитозин и тимин — в качестве символов ленты, цепную реакцию полимеразы для копирования состояния и направленный мутагенез — для его изменения.
Как объясняет профессор Кинг, если, например при поиске в лабиринте электронный компьютер доходит до развилки, то он должен последовательно исследовать каждое ответвление. В отличие от него, ДНК-компьютер не ограничен фиксированным количеством процессоров: он разрастается, реплицируя себя, и изучает все ответвления одновременно. Естественно, что ответ он находит гораздо быстрее.
Квантовые компьютеры тоже могут следовать сразу по всем путям в лабиринте, но только если тот обладает определённой симметрией, что сужает круг решаемых таким методом задач.
«Так как молекулы ДНК очень малы, настольный компьютер может в принципе задействовать больше процессоров, чем используется во всей электронике мира — и превзойти самый быстрый суперкомпьютер, потребляя ничтожную долю расходуемой тем энергии», — подчеркнул Кинг.
Универсальная машина Тьюринга это компьютер, который можно запрограммировать для решения любой вычислительной задачи. Современные электронные компьютеры это разновидность такой универсальной машины, но квантовый ее вариант только предстоит создать. NUTM — машина Тьюринга, способная решать NP-полные задачи за полиномиальное время, до сих пор считалась теоретической абстракцией, которую невозможно реализовать на практике.
Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365
0 |