WikiDer > Система P - Википедия

P system - Wikipedia
Информацию о компьютере p-System см. UCSD p-система.

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

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

Неформальное описание

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

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

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

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

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

Окружение

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

Мембраны

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

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

Символы

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

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

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

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

Правила

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

Существует три (в базовой модели P-системы) различных способов, которыми правило может обрабатывать свои выходные объекты. Обычно выходные объекты передаются в текущую мембрану (ту же мембрану, в которой находятся правило и входы), известную как Вот правило. Однако есть два модификатора, которые могут быть указаны для выходных объектов, когда определены правила: в и вне. В в модификатор вызывает передачу объекта одному из дочерних элементов текущей мембраны (перемещающемуся внутрь относительно структуры P-системы), выбранному в случайный во время расчета. В вне модификатор заставляет объект проходить через текущую мембрану либо в его родительскую мембрану, либо в родственную мембрану, указанную во время спецификации 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-систем.[5]

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

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

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

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

Самая внешняя мембрана, 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 теперь содержит: «диди».

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

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

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

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

Смотрите также

Рекомендации

  1. ^ Пэун, Георге (1998). Вычисления с мембранами. Отчет TUCS 208. Центр компьютерных наук Турку. ISBN 978-952-12-0303-9. Получено 16 декабря 2012.
  2. ^ а б c d Пэун, Георге; Гжегож Розенберг (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.
  4. ^ а б c d е ж Пэун, Георге (2006). «Введение в мембранные вычисления». Приложения мембранных вычислений. Springer Berlin Heidelberg. С. 1–42. ISBN 978-3-540-29937-0.
  5. ^ Фройнд, Рудольф; Кари, Лила; Освальд, Марион; Сосик, Петр (2005). «Вычислительно универсальные P-системы без приоритетов: достаточно двух катализаторов». Теоретическая информатика. 330 (2): 251–266. Дои:10.1016 / j.tcs.2004.06.029. ISSN 0304-3975.
  6. ^ Пэун, Георге (2001). «P-системы с активными мембранами: решение NP-полных проблем» (PDF). Автоматы, языки и комбинаторика. 6 (1): 75–90. Получено 2008-02-03.
  7. ^ Зандрон, Клаудио; Клаудио Ферретти; Джанкарло Маури (2000). «Решение NP-полных задач с использованием P-систем с активными мембранами». Нетрадиционные модели вычислений. С. 289–301. ISBN 1-85233-415-0.

внешняя ссылка

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