Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для компьютерной p-System см. UCSD p-System .

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

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

Неофициальное описание [ править ]

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

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

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

Компоненты системы P [ править ]

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

Окружающая среда [ править ]

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

Мембраны [ править ]

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

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

Символы [ править ]

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

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

Катализаторы [ править ]

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

Правила [ править ]

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

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

Процесс вычисления [ править ]

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

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

Применение правила [ править ]

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

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

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

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

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

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

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

Максимально параллельное приложение [ править ]

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

Как вычислительная модель [ править ]

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

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

Пример вычисления [ править ]

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

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

Внешняя мембрана, 1, является контейнер мембраной для этой системы Р и содержит одну из правила. Мембрана 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 теперь содержит: «диди».

  • "e" присваивается e → e out
  • "e" присваивается e → e out
  • "e" присваивается e → e out
  • "e" присваивается e → e out

Вычисления останавливаются [ править ]

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

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

См. Также [ править ]

  • Клетка (биология)
  • Биологически вдохновленные вычисления
  • Формальный язык
  • Гиперграф
  • MGS
  • Системная биология

Ссылки [ править ]

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

Внешние ссылки [ править ]

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