Мембранные вычисления (или МК ) — это область компьютерной науки , которая стремится открыть новые вычислительные модели из изучения биологических клеток , в частности клеточных мембран . Это подзадача создания клеточной модели .
Мембранные вычисления имеют дело с распределенными и параллельными вычислительными моделями, обрабатывая мультимножества объектов-символов локализованным образом. Таким образом, правила эволюции позволяют инкапсулировать эволюционирующие объекты в отсеки, определяемые мембранами. Связь между отсеками и с окружающей средой играет существенную роль в процессах. Различные типы мембранных систем известны как P-системы в честь Георге Пауна, который первым задумал эту модель в 1998 году. [1]
Важнейшим компонентом P-системы является ее мембранная структура, которая может представлять собой иерархическое расположение мембран, как в клетке, или сеть мембран (размещенных в узлах графа), как в ткани или нейронной сети. P-системы часто изображают графически с помощью рисунков.
Интуиция, лежащая в основе понятия мембраны, — это трехмерная везикула из биологии. Однако сама концепция более общая, и мембрана рассматривается как разделитель двух областей. Мембрана обеспечивает выборочную связь между двумя областями. Согласно Георге Пэуну, разделение происходит в евклидовом пространстве на конечную «внутреннюю» и бесконечную «внешнюю». Выборочная связь — это то, где вступают в дело вычисления.
Графические представления могут иметь многочисленные элементы, в соответствии с вариацией изучаемой модели. Например, правило может производить специальный символ δ, в этом случае мембрана, которая его содержит, растворяется, а все ее содержимое перемещается вверх по иерархии регионов.
Разнообразие предложений из биологии и диапазон возможностей для определения архитектуры и функционирования многосетного устройства обработки на основе мембраны практически бесконечны. Действительно, литература по мембранным вычислениям содержит очень большое количество моделей. Таким образом, МК — это не просто теория, связанная с конкретной моделью, это структура для разработки компартментализированных моделей.
Химикаты моделируются символами или, альтернативно, строками символов. Регион, который определяется мембраной, может содержать другие символы или строки (совместно именуемые объектами) или другие мембраны, так что система P имеет ровно одну внешнюю мембрану, называемую кожной мембраной, и иерархическую связь, управляющую всеми ее мембранами под кожной мембраной.
Если объекты являются символами, то их множественность в пределах региона имеет значение; однако мультимножества также используются в некоторых моделях строк. Регионы имеют связанные правила, которые определяют, как объекты производятся, потребляются, передаются в другие регионы и иным образом взаимодействуют друг с другом. Недетерминированное максимально параллельное применение правил во всей системе является переходом между состояниями системы, а последовательность переходов называется вычислением. Конкретные цели могут быть определены для обозначения состояния остановки, в котором результатом вычисления будут объекты, содержащиеся в определенном регионе. В качестве альтернативы результат может состоять из объектов, отправленных из кожной мембраны в окружающую среду.
Было изучено множество вариантов моделей, и интерес был сосредоточен на доказательстве вычислительной универсальности для систем с небольшим количеством мембран с целью решения NP-полных задач, таких как задачи булевой выполнимости (SAT) и задача коммивояжера (TSP) . Системы P могут торговать пространственно-временными сложностями и реже используют модели для объяснения естественных процессов в живых клетках. Исследования разрабатывают модели, которые, по крайней мере, теоретически могут быть реализованы на оборудовании. На сегодняшний день системы P представляют собой почти все теоретические модели, которые никогда не были приведены к практике, хотя практическая система дана в. [2]
{{cite journal}}: Цитировать журнал требует |journal=( помощь )