Введение
Вычислительная модель
Для компьютерной системы p см. UCSD p System. P-система — это вычислительная модель в области информатики, выполняющая вычисления с использованием процесса, вдохновленного биологией. Они основаны на структуре биологических клеток, абстрагируясь от способов взаимодействия и перемещения химических веществ через клеточные мембраны. Концепция была впервые представлена в отчете 1998 года ученого-компьютерщика Георге Пэуна, чья фамилия является происхождением буквы P в названии "P-системы". Вариации модели P-системы привели к формированию направления исследований, известного как "мембранные вычисления". Хотя P-системы вдохновлены биологией, основной интерес исследований связан с их использованием в качестве вычислительной модели, а не для биологического моделирования, хотя и это направление также изучается.
For the computer p System, see UCSD p System. A P system is a computational model in the field of computer science that performs calculations using a biologically inspired process. They are based upon the structure of biological cells, abstracting from the way in which chemicals interact and cross cell membranes. The concept was first introduced in a 1998 report by the computer scientist Gheorghe Păun, whose last name is the origin of the letter P in 'P Systems'. Variations on the P system model led to the formation of a branch of research known as 'membrane computing.' Although inspired by biology, the primary research interest in P systems is concerned with their use as a computational model, rather than for biological modeling, although this is also being investigated.
Неофициальное описание
Система P определяется как последовательность мембран, содержащих химические вещества (в конечных количествах), катализаторы и правила, определяющие возможные способы взаимодействия химических веществ друг с другом с образованием продуктов. Правила также могут приводить к перемещению химических веществ через мембраны или даже к растворению мембран. Подобно биологической клетке, где химическая реакция может произойти только при случайном столкновении и взаимодействии необходимых химических молекул (возможно, также с катализатором), правила в системе P применяются случайным образом. Это приводит к недетерминированному ходу вычислений, часто приводящему к получению множества решений при повторении вычислений. Система P продолжает работу до тех пор, пока не достигнет состояния, в котором дальнейшие реакции невозможны. В этом случае результатом вычисления являются все химические вещества, прошедшие за пределы внешней мембраны, или же те, которые были направлены в специально выделенную "результатную" мембрану. Как модель вычислений, P-системы предлагают привлекательную возможность решения NP-полных задач за время, меньшее экспоненциального. И, поскольку все NP-полные задачи эквивалентны, эта возможность распространяется на все такие задачи. Поскольку в настоящее время не существует метода непосредственной реализации P-системы как самостоятельной системы, их функциональность эмулируется, и, следовательно, решение NP-полных задач за линейное время остаётся теоретическим. Однако также было доказано, что любая детерминированная P-система может быть смоделирована на машине Тьюринга за полиномиальное время.
Пример расчета
На изображении показано начальное состояние P-системы с тремя мембранами. В силу их иерархической природы, P-системы часто графически изображаются в виде схем, напоминающих диаграммы Венна или гиграфы Дэвида Хареля (см. диаграммы состояний). Самая внешняя мембрана, 1, является контейнерной мембраной для данной P-системы и содержит одно правило вывода. Мембрана 2 содержит четыре правила "здесь", два из которых находятся в отношении приоритета: правило cc → c всегда будет применяться в предпочтении к правилу c → δ. Символ δ (дельта) представляет собой специальный "символ растворения". Внутренняя мембрана, 3, содержит набор символов ("ac") и три правила типа "здесь". В этом начальном состоянии никакие правила за пределами мембраны 3 не могут быть применены: за пределами этой мембраны нет символов. Однако, в процессе эволюции системы, по мере перемещения объектов между мембранами, правила в других мембранах станут активными.
symbols outside of that membrane. However, during evolution of the system, as objects are passed between membranes, the rules in other membranes will become active.
Вычисления
Из-за недетерминированной природы P-систем, одна и та же P-система может иметь множество различных путей вычислений, приводящих к разным результатам. Ниже представлен один из возможных путей вычислений для рассматриваемой P-системы.
Остановка вычислений
Теперь мембрана 1 содержит: "dd" и, вследствие правила выхода e → eout, среда содержит: "eeee". На этом этапе вычисления останавливаются, так как дальнейшее применение правил к объектам невозможно. Результатом вычисления являются четыре символа "e". Единственные недетерминированные выборы произошли на шагах 1 и 2, при выборе места для размещения одиночного символа "a". Рассмотрим случай, когда символ "a" присваивается правилу a → bδ на шаге 1: после растворения мембраны 3 останутся только один объект "b" и два объекта "c", что приведет к созданию только одного объекта "e", который в конечном итоге будет выведен как результат вычисления.
assignments of objects to rules is possible. The result of the computation is four "e" symbols. The only non deterministic choices occurred during steps 1 and 2, when choosing where to assign the solitary "a" symbol. Consider the case where "a" is assigned to a → bδ during step 1: upon membrane 3 dissolving only a single "b" and two "c" objects would exist, leading to the creation of only a single "e" object to eventually be passed out as the computation's result.