П-система

Для компьютерной p-системы см. UCSD p-System .

P - система — это вычислительная модель в области информатики , которая выполняет вычисления с использованием биологических процессов. Они основаны на структуре биологических клеток , абстрагируясь от того, как химические вещества взаимодействуют и проникают через клеточные мембраны . Впервые эта концепция была представлена в отчете 1998 года. ^[1] ученым-компьютерщиком Георге Пауном , чья фамилия является источником буквы P в слове «P Systems». Вариации модели P-системы привели к формированию отрасли исследований, известной как « мембранные вычисления ».

Несмотря на то, что основной исследовательский интерес к P-системам вдохновлен биологией, он связан с их использованием в качестве вычислительной модели, а не для биологического моделирования . ^[2] хотя это тоже расследуется. ^[3]^[4]^[5]

Неофициальное описание

Система AP определяется как серия мембран, содержащих химические вещества (в конечных количествах), катализаторы и правила, которые определяют возможные способы, которыми химические вещества могут взаимодействовать друг с другом с образованием продуктов. Правила могут также привести к прохождению химических веществ через мембраны или даже к их растворению .

Точно так же, как в биологической клетке, где химическая реакция может произойти только в том случайном случае, когда необходимые химические молекулы сталкиваются и взаимодействуют (возможно, также с катализатором), правила в P-системе применяются случайным образом. Это приводит к тому, что вычисления выполняются недетерминированным образом, что часто приводит к появлению нескольких решений, если вычисления повторяются.

Система AP продолжает работать до тех пор, пока не достигнет состояния, в котором дальнейшие реакции невозможны. На этом этапе результатом вычислений являются все те химические вещества, которые прошли за пределы самой внешней мембраны или, иначе говоря, попали в обозначенную «результирующую» мембрану. ^[4]

Компоненты системы P

Хотя существует множество разновидностей системы P, большинство из них имеют одни и те же основные компоненты. Каждый элемент играет определенную роль, и каждый имеет основу в архитектуре биологической клетки, на которой базируются P-системы.

Окружающая среда

Окружающая среда – это окружение системы П. В начальном состоянии P-системы она содержит только мембрану-контейнер, и хотя среда никогда не может содержать правила, в нее могут передаваться объекты во время вычислений. Объекты, обнаруженные в окружающей среде в конце вычислений, составляют весь или часть его «результата».

Мембраны

Мембраны являются основными «структурами» внутри P-системы. Мембрана — это дискретная единица, которая может содержать набор объектов (символов/катализаторов), набор правил и набор других мембран, содержащихся внутри. Внешнюю мембрану, удерживаемую в окружающей среде, часто называют «мембраной-контейнером» или «кожной мембраной». Как следует из их тезки, мембраны проницаемы , и символы, возникающие в результате правил, могут пересекать их. Мембрана (но не мембрана контейнера) также может «растворяться», и в этом случае ее содержимое, за исключением правил (которые теряются), мигрирует в мембрану, в которой оно содержалось. ^[2]

Некоторые варианты P-системы позволяют мембране разделяться, обладать зарядом или иметь различную проницаемость за счет изменения толщины мембраны. ^[2]

Символы

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

Существуют символы специального регистра, например, строчная буква дельта (δ) часто используется для инициирования растворения мембраны, и ее можно найти только в выводе правила: при встрече она вызывает реакцию и используется в процессе.

Катализаторы

Катализаторы похожи на своих однофамильцев в химии. Они представляются и используются так же, как символы, но никогда не потребляются во время « реакции », они просто являются необходимым условием для ее возникновения.

Правила

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

Существует три (в базовой модели P-системы) различных способа обработки выходных объектов правилом. Обычно выходные объекты передаются в текущую мембрану (ту же мембрану, в которой находятся правило и входные данные), известную как правило здесь . Однако есть два модификатора, которые можно указать для выходных объектов при определении правил: in и out . Модификатор in вызывает передачу объекта одному из дочерних элементов текущей мембраны (путешествующему внутрь относительно структуры системы P), выбранному случайным образом во время вычислений. Модификатор out вызывает передачу объекта из текущей мембраны либо в ее родительскую мембрану, либо в родственную мембрану, указанную во время спецификации P-системы.

Процесс расчета

Вычисление происходит от начального начального состояния к конечному состоянию через ряд дискретных шагов. Каждый шаг включает в себя перебор всех мембран в системе P и применение правил, которое происходит как максимально параллельно , так и недетерминировано . ^[4]

Работая шаг за шагом, вычисление останавливается, когда дальнейшая эволюция невозможна (т. е. когда невозможно применить никакие правила). На этом этапе любые объекты, переданные в окружающую среду или в назначенную «результирующую» мембрану, считаются результатом вычислений. ^[4]

Применение правил

На каждом этапе вычислений объект можно использовать только один раз, поскольку при его применении он потребляется правилами. Метод применения правила внутри мембраны следующий:

Назначайте символы из содержимого мембраны на входы правила.
Если все входные данные удовлетворены, удалите все назначенные символы с мембраны.
Создайте выходные символы и удерживайте их до тех пор, пока не будет выполнено все назначение правил для всех мембран.
Добавьте выходные символы к целевым мембранам.
Растворить мембраны при необходимости

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

Недетерминированное приложение

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

Рассмотрим мембрану, содержащую только один символ «а» и два правила a → ab и a → aδ. Поскольку оба правила основаны на наличии символа «а», а он только один, первый шаг вычислений позволит применить либо первое, либо второе правило, но не оба одновременно. Два возможных результата этого шага сильно различаются:

Мембрана переносится на следующий этап вычислений с присутствием как символа «a», так и символа «b», и снова одно из двух правил случайным образом присваивается символу «a».
Мембрана растворяется, и на содержащую мембрану передается один символ «а».

Максимально параллельное приложение

Это свойство применения правил, согласно которому все возможные назначения правил должны выполняться на каждом этапе вычислений. По сути, это означает, что правило a → aa приводит к удвоению количества символов «a» в содержащей его мембране на каждом этапе, поскольку правило применяется к каждому появлению символа «a».

В качестве вычислительной модели

Большинство вариантов P-систем вычислительно универсальны . ^[4] Это распространяется даже на варианты, которые не используют приоритеты правил, что обычно является фундаментальным аспектом P-систем. ^[6]

В качестве модели вычислений P-системы предлагают привлекательную возможность решения NP-полных задач за время, меньшее, чем экспоненциальное . ^[4] Известно, что некоторые варианты P-системы способны решать проблему SAT (булева выполнимость) за линейное время. ^[7] и, поскольку все NP-полные задачи эквивалентны , эта возможность применима ко всем таким задачам. Поскольку в настоящее время не существует метода непосредственной реализации системы P как таковой, вместо этого их функциональность эмулируется. ^[8] и поэтому решение NP-полных задач за линейное время остается теоретическим. Однако также было доказано, что любая детерминированная P-система может быть смоделирована на машине Тьюринга за полиномиальное время . ^[2]

Пример расчета

Графическое представление системы P, которая выводит квадратные числа.

Показанное изображение изображает начальное состояние P-системы с тремя мембранами. Из-за своей иерархической природы P-системы часто изображаются графически с рисунками, напоминающими диаграммы Венна или Дэвида Харела ( Higraph см. Диаграмму состояний ).

Самая внешняя мембрана, 1, является мембраной-контейнером для этой P-системы и содержит единственное правило выхода . Мембрана 2 содержит четыре правила , два из которых находятся в приоритетном отношении: cc → c всегда будет применяться с преимуществом перед c → δ. Символ дельты представляет собой специальный символ «растворения». Самая внутренняя мембрана, 3, содержит набор символов («ac») и три правила типа здесь . В этом исходном состоянии никакие правила за пределами мембраны 3 не применимы: нет никаких правил. символы за пределами этой мембраны. Однако в ходе эволюции системы по мере прохождения объектов между мембранами правила в других мембранах станут активными.

Вычисление

Из-за недетерминированной природы P-систем существует множество различных путей вычислений, на которые способна одна P-система, что приводит к разным результатам. Ниже приведен один из возможных путей вычислений для изображенной системы P.

Шаг 1

Из исходной конфигурации только мембрана 3 имеет объектное содержимое: «ac».

«c» присваивается c → cc
«a» присвоено a → ab

Шаг 2

Мембрана 3 теперь содержит: «abcc»

«a» присваивается a → bδ
«c» присваивается c → cc
«c» присваивается c → cc

Обратите внимание на максимально параллельное поведение применения правил, приводящее к тому, что одно и то же правило применяется дважды за один шаг.

Обратите также внимание, что применение второго правила (a → bδ) в отличие от первого (a → ab) недетерминировано и может считаться случайным. С таким же успехом система могла бы продолжать применять первое правило (и в то же время удваивать количество c-частиц) бесконечно долго.

Мембрана 3 теперь растворяется, поскольку был обнаружен символ растворения (δ), и все содержимое объекта из этой мембраны переходит в мембрану 2.

Шаг 3

Мембрана 2 теперь содержит: «bbcccc».

«b» присваивается b → d
«b» присваивается b → d
«cc» присваивается cc → c
«cc» присваивается cc → c

Шаг 4

Мембрана 2 теперь содержит: «ddcc»

«d» присваивается d → de
«d» присваивается d → de
«cc» присваивается cc → c

Шаг 5

Мембрана 2 теперь содержит: "dedec"

«d» присваивается d → de
«d» присваивается d → de
«c» присваивается c → δ

Обратите внимание, что приоритет над c → δ был повышен, теперь необходимые входные данные для cc → c больше не существуют. Мембрана 2 теперь растворяется, и все содержимое объекта проходит. к мембране 1.

Шаг 6

Мембрана 1 теперь содержит: "deedee"

«e» назначается e → e _out
«e» назначается e → e _out
«e» назначается e → e _out
«e» назначается e → e _out

Вычисления останавливаются

Мембрана 1 теперь содержит: «dd», а из-за правила вывода e → e _out среда содержит: «eeee». На этом этапе вычисление останавливается, так как дальнейшего возможно присвоение объектов правилам. Результатом вычислений являются четыре символа «е».

Единственный недетерминированный выбор произошел на этапах 1 и 2, когда выбирали, куда назначить одиночный символ «а». Рассмотрим случай, когда «a» присваивается a → bδ на этапе 1: после растворения мембраны 3 будут существовать только один объект «b» и два объекта «c», что приведет к созданию только одного объекта «e» для того, чтобы в конечном итоге быть передано как результат вычисления.

См. также

Ссылки

^ Паун, Георге (1998). Вычисления с помощью мембран . Отчет TUCS 208. Центр компьютерных наук Турку. ISBN 978-952-12-0303-9 . Проверено 16 декабря 2012 г.
^ Перейти обратно: ^а ^б ^с ^д Паун, Георге ; Гжегож Розенберг (2002). «Руководство по мембранным вычислениям». Теоретическая информатика . 287 (1): 73–100. CiteSeerX 10.1.1.76.8425 . дои : 10.1016/S0304-3975(02)00136-6 . ISSN 0304-3975 .
^ Арделин, Иоан; Маттео Кавальере (июнь 2003 г.). «Моделирование биологических процессов с использованием вероятностного программного обеспечения p-системы». Естественные вычисления . 2 (2): 173–197. дои : 10.1023/А:1024943605864 . ISSN 1567-7818 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Паун, Георге (2006). «Введение в мембранные вычисления». Применение мембранных вычислений . Шпрингер Берлин Гейдельберг. стр. 1–42. ISBN 978-3-540-29937-0 .
^ Нэш, Энтони; Сара Калвала (2019). «Системная модель роения и агрегации AP в колонии миксобактерий» . Журнал мембранных вычислений . 1 : 103–11. дои : 10.1007/s41965-019-00015-0 .
^ Фройнд, Рудольф; Кари, Лила; Освальд, Мэрион; Сосик, Петр (2005). «Вычислительно универсальные P-системы без приоритетов: достаточно двух катализаторов». Теоретическая информатика . 330 (2): 251–266. дои : 10.1016/j.tcs.2004.06.029 . ISSN 0304-3975 .
^ Паун, Георге (2001). «P-системы с активными мембранами: решение проблем NP-полноты» (PDF) . Автоматы, языки и комбинаторика . 6 (1): 75–90 . Проверено 3 февраля 2008 г.
^ Зандрон, Клаудио; Клаудио Ферретти; Джанкарло Маури (2000). «Решение NP-полных задач с использованием P-систем с активными мембранами». Нетрадиционные модели вычислений . стр. 289–301. ISBN 1-85233-415-0 .

Внешние ссылки

P Systems - веб-сайт для исследований P-систем.

[1] Паун, Георге (1998). Вычисления с помощью мембран . Отчет TUCS 208. Центр компьютерных наук Турку. ISBN 978-952-12-0303-9 . Проверено 16 декабря 2012 г.

[paun2002-2] Перейти обратно: ^а ^б ^с ^д Паун, Георге ; Гжегож Розенберг (2002). «Руководство по мембранным вычислениям». Теоретическая информатика . 287 (1): 73–100. CiteSeerX 10.1.1.76.8425 . дои : 10.1016/S0304-3975(02)00136-6 . ISSN 0304-3975 .

[3] Арделин, Иоан; Маттео Кавальере (июнь 2003 г.). «Моделирование биологических процессов с использованием вероятностного программного обеспечения p-системы». Естественные вычисления . 2 (2): 173–197. дои : 10.1023/А:1024943605864 . ISSN 1567-7818 .

[paun2006-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж Паун, Георге (2006). «Введение в мембранные вычисления». Применение мембранных вычислений . Шпрингер Берлин Гейдельберг. стр. 1–42. ISBN 978-3-540-29937-0 .

[5] Нэш, Энтони; Сара Калвала (2019). «Системная модель роения и агрегации AP в колонии миксобактерий» . Журнал мембранных вычислений . 1 : 103–11. дои : 10.1007/s41965-019-00015-0 .

[6] Фройнд, Рудольф; Кари, Лила; Освальд, Мэрион; Сосик, Петр (2005). «Вычислительно универсальные P-системы без приоритетов: достаточно двух катализаторов». Теоретическая информатика . 330 (2): 251–266. дои : 10.1016/j.tcs.2004.06.029 . ISSN 0304-3975 .

[7] Паун, Георге (2001). «P-системы с активными мембранами: решение проблем NP-полноты» (PDF) . Автоматы, языки и комбинаторика . 6 (1): 75–90 . Проверено 3 февраля 2008 г.

[8] Зандрон, Клаудио; Клаудио Ферретти; Джанкарло Маури (2000). «Решение NP-полных задач с использованием P-систем с активными мембранами». Нетрадиционные модели вычислений . стр. 289–301. ISBN 1-85233-415-0 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]