Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Построена ингибиторная сеть Петри с фиксированной структурой, которая исполняет произвольную заданную машину Тьюринга. Лента машины Тьюринга, ее программа и состояния зашифрованы маркировкой 10 выделенных позиций сети Петри. Правила работы машины Тьюринга закодированы одиночным потоком управления в...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2012 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/50161 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 26-41. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50161 |
|---|---|
| record_format |
dspace |
| spelling |
Зайцев, Д.А. 2013-10-06T13:49:55Z 2013-10-06T13:49:55Z 2012 Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 26-41. — Бібліогр.: 12 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50161 519.74 Построена ингибиторная сеть Петри с фиксированной структурой, которая исполняет произвольную заданную машину Тьюринга. Лента машины Тьюринга, ее программа и состояния зашифрованы маркировкой 10 выделенных позиций сети Петри. Правила работы машины Тьюринга закодированы одиночным потоком управления в сети Петри, скомпонованной из операторов последовательности, ветвления, цикла. Использованы подсети, реализующие операции арифметики, сравнения, копирования. Побудовано інгібіторну мережу Петрі з фіксованою структурою, яка виконує довільну задану машину Тюрінга. Стрічка машини Тюрінга, її програма та стани зашифровані маркуванням 10-ти виділених позицій мережі Петрі. Правила роботи машини Тюрінга закодовано одиночним потоком управління в мережі Петрі, яка скомпонована із операторів послідовності, розгалуження, циклу. Використано підмережі, що реалізують операції арифметики, порівняння, копіювання. The inhibitor Petri net with a fixed structure that executes an arbitrary given Turing machine was constructed. The tape of the Turing machine, its program and states are encoded by the marking of 10 dedicated places of the Petri net. The rules of Turing machine work are encoded by a single control flow within the inhibitor Petri net, which is composed of the sequence operators, branching, and cycle. Subnets which implement arithmetic, comparison and copying operations are used. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга Інгібіторна мережа Петрі, яка виконує довільну задану машину Тюрінга Inhibitor Petri Net, which performs any given Turing machine Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга |
| spellingShingle |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга Зайцев, Д.А. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| title_short |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга |
| title_full |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга |
| title_fullStr |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга |
| title_full_unstemmed |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга |
| title_sort |
ингибиторная сеть петри, исполняющая произвольную заданную машину тьюринга |
| author |
Зайцев, Д.А. |
| author_facet |
Зайцев, Д.А. |
| topic |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| topic_facet |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Інгібіторна мережа Петрі, яка виконує довільну задану машину Тюрінга Inhibitor Petri Net, which performs any given Turing machine |
| description |
Построена ингибиторная сеть Петри с фиксированной структурой, которая исполняет произвольную заданную машину Тьюринга. Лента машины Тьюринга, ее программа и состояния зашифрованы маркировкой 10 выделенных позиций сети Петри. Правила работы машины Тьюринга закодированы одиночным потоком управления в сети Петри, скомпонованной из операторов последовательности, ветвления, цикла. Использованы подсети, реализующие операции арифметики, сравнения, копирования.
Побудовано інгібіторну мережу Петрі з фіксованою структурою, яка виконує довільну задану машину Тюрінга. Стрічка машини Тюрінга, її програма та стани зашифровані маркуванням 10-ти виділених позицій мережі Петрі. Правила роботи машини Тюрінга закодовано одиночним потоком управління в мережі Петрі, яка скомпонована із операторів послідовності, розгалуження, циклу. Використано підмережі, що реалізують операції арифметики, порівняння, копіювання.
The inhibitor Petri net with a fixed structure that executes an arbitrary given Turing machine was constructed. The tape of the Turing machine, its program and states are encoded by the marking of 10 dedicated places of the Petri net. The rules of Turing machine work are encoded by a single control flow within the inhibitor Petri net, which is composed of the sequence operators, branching, and cycle. Subnets which implement arithmetic, comparison and copying operations are used.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50161 |
| citation_txt |
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 26-41. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT zaicevda ingibitornaâsetʹpetriispolnâûŝaâproizvolʹnuûzadannuûmašinutʹûringa AT zaicevda íngíbítornamerežapetríâkavikonuêdovílʹnuzadanumašinutûrínga AT zaicevda inhibitorpetrinetwhichperformsanygiventuringmachine |
| first_indexed |
2025-11-26T09:19:09Z |
| last_indexed |
2025-11-26T09:19:09Z |
| _version_ |
1850617392156114944 |
| fulltext |
© Д.А. Зайцев, 2012
26 ISSN 1681–6048 System Research & Information Technologies, 2012, № 2
УДК 519.74
ИНГИБИТОРНАЯ СЕТЬ ПЕТРИ, ИСПОЛНЯЮЩАЯ
ПРОИЗВОЛЬНУЮ ЗАДАННУЮ МАШИНУ ТЬЮРИНГА
Д.А. ЗАЙЦЕВ
Построена ингибиторная сеть Петри с фиксированной структурой, исполняю-
щая произвольную заданную машину Тьюринга. Лента машины Тьюринга, ее
программа и состояния зашифрованы маркировкой 10-ти выделенных позиций
сети Петри. Правила работы машины Тьюринга закодированы одиночным по-
током управления в сети Петри, скомпонованной из операторов последова-
тельности, ветвления, цикла. Использованы подсети, реализующие операции
арифметики, сравнения, копирования.
ВВЕДЕНИЕ
Известно, что ингибиторная сеть Петри представляет собой универсальную
алгоритмическую систему [1, 2]. Доказательство было получено на основе
моделирования счетчиковой машины Минского ингибиторной сетью Петри
[2] и предполагает индивидуальное кодирование программы каждой задан-
ной машины Минского графом ингибиторной сети Петри.
Цель работы — построение ингибиторной сети с фиксированной
структурой (графом), исполняющая произвольную заданную машину Тью-
ринга [3, 4] на основе шифрования машины Тьюринга маркировкой фикси-
рованного числа позиций сети Петри.
Помимо указанной цели, при наличии обоих: IPNTM (Inhibitor Petri Net
Turing Machine — ингибиторная сеть Петри, исполняющая машину Тьюрин-
га) и TMIPN (Turing Machine Inhibitor Petri Net — машина Тьюринга, испол-
няющая ингибиторную сеть Петри) — их композиция дает новый способ
построения универсальной ингибиторной сети Петри [5], а также универ-
сальной машины Тьюринга [6]. Действительно, IPNTM (TMIPN) является
универсальной ингибиторной сетью Петри: она принимает на вход шифр
заданной ингибиторной сети Петри для машины Тьюринга TMIPN и затем
исполняет машину Тьюринга TMIPN, зашифрованную для IPNTM. И наобо-
рот, TMIPN (IPNTM) является универсальной машиной Тьюринга: она при-
нимает на вход шифр заданной машины Тьюринга для ингибиторной сети
Петри IPNTM и затем исполняет ингибиторную сеть Петри IPNTM, зашиф-
рованную для TMIPN.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
Ингибиторная сеть Петри
Граф ингибиторной сети Петри [1, 2] является взвешенным двудольным
ориентированным графом, представленным четверкой ),,,,( DBTPG = где
},...,{ 1 mppP = — конечное число вершин именуемых позициями;
},...,{ 1 nttT = — конечное число вершин именуемых переходами, а отобра-
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 27
жения }1{: −∪Ν→×TPB и Ν→× PTD : задают входные и выходные
дуги переходов вместе с их кратностью; Ν — множество целых неотрица-
тельных чисел; нулевое значение отображений — DB, — обозначает от-
сутствие дуги; ненулевое — кратность дуги, специальное значение 1−
задает ингибиторную дугу. Отображения могут быть представлены соот-
ветствующими матрицами: ),(, ,, ijjiji tpBbbB == и == jiji ddD ,, ,
).,( ji ptD=
Состояние сети именуется маркировкой и представлено отображением
,: Ν→PQ которое задает количество динамических элементов — фишек
внутри позиций сети. Ингибиторная сеть Петри (ИСП) [1, 2] — это пара
),,( 0QGN = где G — граф сети, а 0Q — ее начальная маркировка. Мар-
кировка может быть представлена соответствующим вектором: ,jqQ =
).( jj pQq = Таким образом, ингибиторная сеть Петри задана парой чисел,
парой матриц и вектором ).,,,,( 0QDBnmN = Динамика ингибиторной сети
представляет собой пошаговый процесс изменения ее маркировки в резуль-
тате срабатывания переходов и может быть описана уравнением состоя-
ний [5].
Позиции изображают окружностями с фишками в виде точек, разме-
щенными внутри них, переходы — прямоугольниками. Для графического
представления ингибиторной дуги используют полую окружность на конце
дуги. Дуга с заполненной окружностью на конце обозначает пару дуг про-
тивоположного направления и равной кратности, она используется для про-
верки маркировки позиции (без ее изменения).
Машина Тьюринга
Машина Тьюринга (MТ) [3] — это шестерка ),,,,,,( fs qqPVQXM = , где
X — конечный алфавит символов ленты, содержащий пустой символ λ ;
Q — конечный алфавит внутренних состояний; sq — начальное состояние;
fq — конечное (заключительное) состояние; },,{ rslV = — алфавит пере-
мещений соответственно (влево, стоять, вправо); P — функция переходов
(программа), представленная как:
• отображение для детерминированной машины Тьюринга
;: VQXQXP ××→×
• отношение для недетерминированной машины Тьюринга
).()( VQXQXP ××××⊆
Конструкция машины Тьюринга следующая:
1) бесконечная в обоих направлениях лента разделена на ячейки, со-
держащие символ алфавита .X Изначально все ячейки заполнены пустым
символом λ ;
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 28
2) управляющая головка движется вдоль ленты, на текущем шаге обо-
зревает одну текущую ячейку и находится во внутреннем состоянии ;q
3) программа (функция переходов) P задает переход машины Тьюрин-
га на следующий шаг.
Правила перехода на следующий шаг:
а) останавливается, если jqq = ,.
б) управляющая головка считывает символ x из текущей ячейки,
в) находит соответствующую команду ),,(),( vxqxq ′′→ в ,P
г) записывает символ x′ в текущую ячейку,
д) перемещается на одну ячейку влево, вправо, либо остается на месте
в зависимости от значения ,v
е) переключается в следующее состояние qq ′=: и продолжает по пра-
вилу (a).
Выбор команды в соответствии с правилом (в) уникален для детерми-
нированной машины Тьюринга и множественен для недетерминированной
машины Тьюринга [4]. Без ограничения общности рассмотрено только одно
заключительное состояние. Определение машины Тьюринга с множеством
заключительных состояний может быть преобразовано путем добавления
команд перехода в единственное заключительное состояние без изменения
текущего символа и перемещения головки.
Минимальную часть ленты, заполненную не пустыми символами, на-
зывают рабочей зоной. Обычно предполагают, что машина начинает (и за-
вершает) свою работу в положении головки над крайней левой ячейкой ра-
бочей зоны. В качестве начальной рабочей зоны слово α в алфавите X
записано на ленте. После останова машины слово ,β полученное в рабочей
зоне, рассматривается как результат.
ШИФРОВАНИЕ МАШИНЫ ТЬЮРИНГА
В настоящем разделе представлено шифрование машины Тьюринга, вклю-
чая ленту с позицией управляющей головки, текущее и заключительное
состояния, программу, в форме маркировок десяти выделенных позиций
сети IPNTM: ,sL x , sR , ,rX ,q ,qf rQ , ,sP ,rP .rV Шесть дополни-
тельных позиций использованы для хранения текущей команды и ее компо-
нентов: sI , Iq , Ix , Jq , Jx , .Iv Пример шифрования машины описан далее
в подразделе «Пример шифрования машины Тьюринга».
Шифрование алфавитов и выделенных состояний МТ
Зашифруем символы алфавитов VQX ,, целыми неотрицательными числа-
ми диапазона от нуля до 1,1,1 −−− VQX соответственно. При шифро-
вании алфавита X будем предполагать, что пустой символ зашифрован ну-
лем. Шифрование алфавита V следующее: 2,0,1 →↔↔ rsl . Остальное
шифрование произвольное.
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 29
Для работы с шифрами алфавитов использованы три позиции TPNTM
с именами rVrQrX ,, содержащие следующие значения: ,XrX = ,QrQ =
VrV = .
Определение МТ содержит два выделенных состояния ,, fs qq и во
время работы МТ рассматривается текущее состояние ,q совпадающее с
начальным состоянием при запуске машины sqq = . Выделенные состояния
представлены двумя позициями IPNTM с именами ,,qfq которые содержат
шифры текущего и заключительного состояния соответственно; предпола-
гается, что шифр sq изначально загружен в позицию .q
Шифрование программы
Использовано рекуррентное шифрование и дешифрование векторов неотри-
цательных целых [5]:
1,1,, 1011 −==+= −−−− mjasarss mjmjj , (1)
ssrssrsa mjmjmjmj === −−−+−−−− 11)1(11 ,div,mod , 1,0 −= mj , (2)
где шифр вектора A длины m равен 1−= mss , а основание шифрования
1max += j
j
ar .
Для шифрования программа (функция переходов) P рассматривается
как множество команд (инструкций) }{IP = в форме ),,,,,( vxqxqI ′′=
компонентами которых являются шифры состояний, символов текущей
ячейки, движения головки. Заметим, что недетерминированная МТ может
содержать несколько команд с одинаковой парой ).,( xq
Команда зашифрована как вектор (1) с переменной величиной основа-
ния r : ).,,,,( rXrQrXrQrV Заметим, что rV реально не используется, так
как вычисляется ее нулевая степень. Выраженное в явной форме шифрова-
ние имеет вид:
).()()( rXrQrXrQvrQrXrQxrQrXqxrQqsI +′+′++= (3)
Выполненные построения дают неоднозначную интерпретацию нуля
как шифра инструкции ),,,,,( 00000 vxqxq что может быть неудобным при
неизвестной длине программы. Либо указанная фиктивная команда должна
быть исключена из рассмотрения, либо некоторые шифры (например )V
должны начинаться с единицы.
Множество команд занумеровано в произвольном порядке, начиная
с нуля до 1−= Pk , для использования простого алгоритма последователь-
ного поиска. Таким образом, программа представлена как вектор
).,...,,( 110 −= kIIIP Для ее шифрования как вектора (1) следует выбрать
значение требуемого основания. Максимальный возможный шифр команды
следующий:
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 30
+−+−+−+−= )()1()()1()1()1(max rQrXrQrXrXrQrQrQrXrQsI
).)(1( rXrQrXrQrV −+
Таким образом, основание для шифрования программы имеет значение
1max += sIrP . (4)
Итак, программа МТ представлена двумя позициями IPNTM с именами
,, rPsP которые содержат значения rPsP, соответственно. Дополнитель-
ные позиции использованы для хранения текущей команды ),,,,( vxqxqI ′′=
и ее компонентов IvJxJqIxIqsI ,,,,, соответственно (для последовательного
поиска подходящей команды).
Шифрование ленты
Шифрование рабочей зоны ленты может быть выполнено также, как и шиф-
рование программы, но в этом случае необходима дополнительная инфор-
мация о текущей позиции управляющей головки.
Заметим, что рекуррентное шифрование (1) и дешифрование (2) задают
дисциплину стека (LIFO). Начнем с нулевого значения 0=s , тогда опера-
ции
xrssxrsADDMULsx +⋅== :::),,(_),(push ,
rssrsxxrsDIVMODspop div:,mod:::),,(_)( ===
обеспечивают дисциплину стека, и достижение дна стека распознается как
условие .0=s Неоднозначность шифрования в случае, когда нулевой шифр
представляет пустой символ λ , является полезной. Последовательное де-
шифрование нуля дает неограниченное количество символов λ на дне сте-
ка. «Бездонное дно» дает возможность представить две части ленты по
обеим сторонам текущей ячейки как два стека.
Символы рабочей зоны ленты занумерованы следующим образом:
,...,,...,,,,,...,,,..., 110021 λλ −−− nmm RRRxLLL ,
где iL — символы левой части, а jR — символы правой части ленты отно-
сительно символа текущей ячейки x . Обе части ленты зашифрованы как
векторы RL, в соответствии с (1). Полученные шифры обозначены как
sRsL, соответственно.
Лента и текущая позиция управляющей головки зашифрованы как три
неотрицательных целых числа ),,,( sRxsLsT = где sL — шифр левой час-
ти рабочей зоны, sR — шифр правой части рабочей зоны, x — шифр сим-
вола текущей ячейки. Основание для шифрования соответствует алфавиту
ленты .rXr =
Описанное шифрование обеспечивает следующую реализацию пере-
мещений управляющей головки:
)(pop:),,(push::),,(left sLxsRxsRxsL = ,
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 31
>< измененийбез::),,(stay sRxsL ,
)(pop:),,(push::),,(right sRxsLxsRxsL = . (5)
Итак, лента и позиция управляющей головки представлены тремя по-
зициями IPNTM с именами sRxsL ,, , которые содержат значения sRxsL ,,
соответственно.
Пример шифрования машины Тьюринга
Построим машину Тьюринга МТ1, которая переводит числа из унарной
в бинарную систему счисления: }1,0,,{ aX λ= , },,,,,{ 543210 qqqqqqQ = ,
0qqs = , 5qq f = ; в унарной системе счисления символ a использован для
представления числа.
Шифры алфавитов, программы и процесса работы МТ1 представлены в
табл. 1, 2, 3 соответственно; программа не является полностью определен-
ной: для краткости опущены команды для некорректных конфигураций.
Т а б л и ц а 1 . Шифрование алфавитов МТ1
Алфавит X Алфавит Q
λ a 0 1 0q 1q 2q 3q 4q 5q
rX rQ rP
0 1 2 3 0 1 2 3 4 5 4 6 1728
Т а б л и ц а 2 . Шифрование программы МТ1
№ Команда sI sP
0 0 1 0 1 2 1302 1302
1 0 2 0 2 2 1452 2251308
2 0 3 0 3 2 1602 3890261826
3 0 0 1 0 1 600 6722372435928
4 1 1 2 0 1 631 11616259569284215
5 1 2 4 2 1 973 20072896535723124493
6 1 3 4 3 1 1123 34685965213729559125027
7 2 1 2 1 1 776 59937347889324678168047432
8 2 2 0 3 2 1598 103571737152753043874385964094
9 2 0 0 3 2 1586 178971961799957259814938945956018
10 2 3 3 2 1 956 309263549990326144960214498612000060
11 3 3 3 2 1 957 534407414383283578491250653601536104637
12 3 2 0 3 2 1599 923456012054314023632881129423454388814335
13 3 0 0 3 2 1587 1595731988829854632837618591643729183871172467
14 4 2 4 2 1 976 2757424876697988805543404926360364029729386023952
15 4 3 4 3 1 1126 4764830186934124655979003712750709043372379049390182
16 4 0 5 0 2 1276 8233626563022167405531718415633225226947470997346235772
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 32
КОДИРОВАНИЕ АЛГОРИТМОВ ИНГИБИТОРНОЙ СЕТЬЮ ПЕТРИ
Сети Петри известны как форма представления параллельных (concurrent)
алгоритмов и вычислений, управляемых потоками данных (data flow) [2, 7,
8]. В большинстве случаев, алгоритмы моделируются сетями Петри, что оз-
начает определенный акт абстрагирования, приводящий к утрате некоторых
особенностей. Такое абстрагирование обычно оправдано общей целью ис-
следования, например, поиском взаимных блокировок (тупиков), верифика-
цией протокола и т.п.
Шифр ленты
Шаг Лента
sL x sR
Сост.
q
№
ком.
0 aaaa
^ 0 1 21 0 0
1 aaaa
^ 1 1 5 0 0
2 aaaa
^ 5 1 1 0 0
3 aaaa
^ 21 1 0 0 0
4 aaaaλ
^
85 0 0 0 3
5 aaaa
^ 21 1 0 1 4
6 aaaλ
^
5 1 0 2 7
7 aaa
^ 1 1 1 2 7
8 aaa
^ 0 1 5 2 7
9 λaaa
^
0 0 21 2 9
10 1aaa ^ 3 1 5 0 0
11 1aaa ^ 13 1 1 0 0
12 1aaa ^ 53 1 0 0 0
13 1aaaλ
^
213 0 0 0 3
14 1aaa ^ 53 1 0 1 4
15 1aaλ
^
13 1 0 2 7
16 1aa ^ 3 1 1 2 7
17 1aa ^ 0 3 5 2 10
18 λ0aa
^
0 0 22 3 13
19 10aa ^ 3 2 5 0 1
Шифр ленты
Шаг Лента sL x sR
Сост.
q
№
ком.
20 10aa
^ sL x sR 0 0
21 10aa
^ 57 1 0 0 0
22 10aaλ
^
229 0 0 0 3
23 10aa
^ 57 1 0 1 4
24 10aλ
^
14 1 0 2 7
25 10a
^ 3 2 1 2 8
26 11a
^ 15 1 0 0 0
27 11aλ
^
61 0 0 0 3
28 11a
^ 15 1 0 1 4
29 11λ
^
3 3 0 2 10
30 10
^ 0 3 2 3 11
31 λ00
^
0 0 10 3 13
32 100
^ 3 2 2 0 1
33 100
^ 14 2 0 0 1
34 100λ
^
58 0 0 0 3
35 100
^ 14 2 0 1 5
36 100
^ 3 2 2 4 14
37 100
^ 0 3 10 4 15
38 λ100
^
0 0 43 4 16
39 100
^ 0 3 10 5
Т а б л и ц а 3 . Шифрование процесса работы МТ1
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 33
В настоящей работе внимание сконцентрировано на точной специфи-
кации одного потока управления, который описывает правила работы МТ.
Для этих целей конструкции, рассмотренные в [1, 2], специфицированы бо-
лее строго с точным разделением элементов сети Петри на две категории:
для описания переменных и для описания одного потока управления. Ука-
занное разделение выполнено до определенных границ: выбраны подсети,
которые представляют множество базисных операций, необходимых для
выполнения МТ. Для этих подсетей представлено доказательство их кор-
ректности в явном виде.
Каждый оператор (операция, процедура) представлен подсетью вида,
изображенного на рис. 1. Для передачи параметров использованы контакт-
ные позиции, которые разделены на входные и выходные. Две выделенные
позиции start (s) и finish )( f представляют поток управления. Для обеспече-
ния повторного прохождения потока управления через операторы, примем
следующие соглашения: все внутренние позиции имеют нулевую маркиров-
ку; перед запуском оператора все входные переменные копируются во вход-
ные позиции оператора; работа оператора запускается попаданием фишки в
позицию s; оператор завершает свою работу при попадании фишки в пози-
цию ;f при завершении работы оператора все его позиции пусты за исклю-
чением выходных позиций, которые содержат результат.
Рассматривается два вида переменных: глобальные статические и па-
раметры операторов. Композиция статических переменных и параметров
выполняется как совмещение (объединение) соответствующих позиций.
Композиция (синхронизация [1]) потока управления и переменных обеспе-
чивается парой выделенных позиций s и ,f которые совмещаются при су-
перпозиции операторов — f предыдущего совмещается с s следующего.
Каждая статическая глобальная переменная представлена соответст-
вующей позицией сети Петри (рис. 2). Поток управления моделируется
Оператор
s f
Входные
позиции
Выходные
позиции
Рис. 1. Представление оператора
start
Переменные
Поток управления
finish
Рис. 2. Представление алгоритма
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 34
трассой прохождения одной фишки из начальной позиции )(start s в завер-
шающую позицию ).(finish f
Введены пунктирные дуги [5], обозначающие следующие дополни-
тельные правила формирования значений входных и выходных позиций:
при запуске содержимое переменной копируется во входную переменную
оператора; после завершения переменная очищается, и в нее перемещается
значение выходной позиции оператора. В случае нескольких переменных
строятся цепочки COPY для последовательного копирования входных пере-
менных и цепочки CLEAN, MOVE для перемещения значений выходных пе-
ременных. Последовательность CLEAN, MOVE обозначена как ASSIGN.
Лемма 1. Алгоритмические управляющие структуры могут быть зако-
дированы ингибиторной сетью Петри в форме, представленной на рис. 3.
Доказательство. Представим доказательство для структуры ветвления
(рис. 3, б). В начальной маркировке 11 =p разрешен только переход 1t , ко-
торый срабатывает и помещает значение условия в позицию 3p и фишку
потока управления в позицию 4p . Допустим, что истинное значение пред-
ставлено единичной маркировкой, а ложное — нулевой маркировкой. По-
этому только один из переходов 32 , tt разрешен, а именно: 2t в единичной
маркировке 3p и 3t в нулевой маркировке. При срабатывании 2t фишка
потока управления перемещается в позицию 5p , что запускает переход 4t ,
а при срабатывании 3t фишка потока управления перемещается в позицию
6p , что запускает переход 5t . В итоге фишка потока управления попадает
в позицию 2p , а все другие позиции пусты. Следовательно, разрешены
p3
c
p4
f/s
t3
t2
p5
s
t4
operator
t1
condition
p1
s
p2
f
p6
f
t5
p1
s
t1
operator1
p2
f/s
t2
operator2
p3
f
p3
c
p4
f/s
t3
t2
p5
s
p6
s
t4
operator1
t5
operator2
p2
f
t1
condition
p1
s
а
б
в
Рис. 3. Кодирование алгоритмических управляющих структур, где а — последова-
тельность, б — ветвление, в — цикл (while)
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 35
только две последовательности срабатывания 421 ttt или 531 ttt , что означает
выбор операторов operator1 или operator2 после вычисления условия condi-
tion; operator1 выбран, когда значение условия истинно, а operator2 — когда
ложно, что соответствует семантике структуры ветвления.
Заметим, что в соответствии с рис. 3, a, суперпозиция операторов при
кодировании алгоритма осуществляется совмещением выходной позиции f
первого оператора с входной позицией s второго оператора.
Известны примеры представления основных алгебраических и логи-
ческих операций сетями Петри [2, 9, 10]. В некоторых случаях удобно непо-
средственное представление наиболее часто выполняемых действий, таких
как, например, MOD_DIV и MUL_ADD для дешифрования и шифрования
МТ. В построениях IPNTM использованы вспомогательные сети, изученные
в [5].
КОМПОЗИЦИЯ IPNTM
Закодируем правила работы МТ рассмотренные в подразделе «Машина
Тьюринга» ингибиторной сетью Петри в соответствии с принципами, опи-
санными в разделе «Кодирование алгоритмов ингибиторной сетью Петри» и
шифрованием МТ, описанным в разделе «Шифрование машины Тьюринга».
Заметим, что леммы 1, 2 перечисляют все требуемые управляющие структу-
ры и операции. Получена сеть IPNTM, представленная на рис. 4.
При построении IPNTM выполнено последовательное соединение под-
сетей, реализующих правила (a)–(е) работы МТ, и организован основной
цикл повторения шага. Подсеть EQ проверяет достижение заключительного
состояния (правило (a)); подсеть FIND_I выполняет поиск подходящей ко-
манды (правила (б)–(в)); подсеть EXEC_I реализует выполнение найденной
команды (г)–(е); ветвление после FIND_I реализует аварийный останов в
случае отсутствия подходящей команды, подсеть FIND_I представляет со-
бой суперпозицию цикла, двух ветвлений и последовательностей; подсеть
EXEC_I представляет собой суперпозицию двух ветвлений и последова-
тельностей для выбора одного из трех вариантов перемещения головки.
Для представления переменных использованы совмещенные позиции:
все позиции с одинаковыми именами логически являются одной и той же
позицией; совмещенные позиции облегчают графическое представление се-
ти. Предполагаем, что перед запуском сети IPNTM шифр целевой (испол-
няемой) МТ загружен в выделенные позиции, а после останова сети IPNTM
шифр полученной МТ (ее ленты) считан из соответствующих позиций.
Пунктирные линии обозначают рассмотренные в разделе «Кодирование
алгоритмов ингибиторной сетью Петри» соглашения по копированию вход-
ных и выходных переменных. Двунаправленные дуги использованы для ра-
боты с переменными, которые являются как входными, так и выходными.
В этом случае копирование может быть оптимизировано двукратным при-
менением MOVE без очистки. В некоторых случаях для копирования вход-
ной переменной вместе с ее очисткой целесообразно использовать MOVE
вместо COPY. В качестве соответствующего обозначения использована ли-
ния с точечным пунктиром. Подстановка перехода подразумевает копиро-
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 36
вание соответствующей подсети с совмещением контактных позиций.
В общем случае подстановка перехода требует указание отображения вход-
ных и выходных позиций. В приведенных сетях отображение задано неявно
контекстом использованных операций и не указано дополнительно.
Теорема 1. Сеть IPNTM исполняет произвольную заданную детерми-
нированную машину Тьюринга.
Доказательство. Докажем, что работа IPNTM полностью соответст-
вует правилам работы МТ, описанным в подразделе «Машина Тьюринга»
относительно шифрования МТ, описанного в разделе «Шифрование маши-
ны Тьюринга». Сеть IPNTM использует три подсети FIND_I, DA_I, EXEC_I
для нахождения подходящей команды, разбора (дизассемблирования) ко-
манды, исполнения команды соответственно, а также операции, представ-
ленные в [5] сетями Петри.
Во-первых, сеть IPNTM (рис. 4, а) реализует требуемую последова-
тельность правил (а)–(е): в цикле (начинающемся с )3p она сравнивает
(EQ) текущее состояние q с заключительным состоянием fq и выходит из
цикла ( 7t ) в случае совпадения в соответствии с правилом (a); чтение теку-
щего символа по правилу (б) не требуется, поскольку символ текущей ячей-
ки ленты (его шифр) выделен в позиции x в соответствии с шифрованием
МТ. Затем она находит подходящую команду (FIND_I) и исполняет ее
(EXEC_I). Для проверки возможных ошибок добавлены дополнительные
позиции, названные found и noi. В случае отсутствия подходящей команды
подсеть FIND_I не помещает фишку в позицию found и IPNTM выходит из
цикла с фишкой в позиции noi (нет команды).
Требуется доказать, что сеть FIND_I находит подходящую команду
в оответствии с правилом (в), и сеть EXEC_I исполняет найденную команду
в соответствии с правилами (г)–(е).
Сеть FIND_I копирует шифр программы во вспомогательную позицию
sP1 и обрабатывает sP1 в цикле (начинающемся с 3p ). Имеется два возмож-
ных выхода из цикла: позитивный ( 11t ) — найдена подходящая команда,
негативный ( 2t ) — все команды были проанализированы и подходящая ко-
манда не найдена (sP1==0). В цикле, операция MOD_DIV извлекает теку-
щую команду из шифра программы sP1, разбирает текущую команду, ис-
пользуя подсеть DA_I, и сравнивает последовательно текущее состояние
и текущий символ команды с текущим состоянием головки q и текущим
символом ленты x. В случае любого несовпадения ( qIq =! или xIx =! ) она
возвращается к началу цикла ( 9t или 12t ). Когда и состояние, и символ ко-
манды совпадают с текущими значениями в соответствии с правилом (c),
она выходит из цикла ( 11t ) с размещением фишки в позиции found. Заме-
тим, что разобранные компоненты найденной команды сохраняются в пози-
циях IvJxJqIxIq ,,,, .
Сеть DA_I разбирает команду в соответствии с принципами, описан-
ными в подразделе «Шифрование ленты»: она применяет четыре последова-
тельных операции MOD_DIV с различными значениями основания .r Заме-
тим, что в соответствии с (4) не требуется применять MOD_DIV пять раз,
так как четвертое деление дает ,vI а остаток — .Jx
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 37
p5
t4
FI
N
D
_I
p6
p1
2 fo
un
d
t5
p7
t6
EX
EC
_I
p8
p3
lo
op
t2
EQ
p9
q
p4
t3
q!
=q
f
p1
0
qf
p1
1
c
p1
s
t1
t7
q=
=q
f
t9
t8
p2
f
p1
3
no
i
p1
s
t0
AS
SI
G
N
p1
0
sP
p3
w
hi
le
t1
sP
1>
0
p1
1
sP
1
p4
t3
M
O
D
_D
IV
p5
t4
D
A_
I
p6
p1
4
Iq
t5
EQ
p1
5
q
p7
p1
6
c
t8
Iq
==
q p8
t1
0
EQ
p1
7
Ix
p1
8 x
p9
p1
9
c
t1
1
Ix
==
x
t9
Iq
!=
q
p2
0
fo
un
d
p2
f
t2
sP
1=
=0
t1
2 Ix
!=
x
p1
3
sI
p1
2
rX
а б
Ри
с.
4
. И
нг
иб
ит
ор
на
я
се
ть
П
ет
ри
IP
N
TM
, и
сп
ол
ня
ю
щ
ая
м
аш
ин
у
Ть
ю
ри
нг
а,
г
де
а
—
IP
N
TM
, б
—
F
IN
D
_I
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 38
в
г
t2
M
O
D
_D
IV
p6
sI
p8
Iq
p7
rQ
p9
sI
p1
1
Ix
p1
0
rX
p3
p1
s
p4
t3
M
O
D
_D
IV
p1
2 sI
p1
4
Jq
p1
3
rQ
p5
t4
M
O
D
_D
IV
p1
5 sI
p1
7
Jx
p1
6
rX
t1
M
O
D
_D
IV
p2
f
p1
8
Iv
p1
s
t6
AS
SI
G
N
p2
3
Jq
p2
4
q
t1
AS
SI
G
N
p1
0
Jx
p1
1
x
p2
f
p3
t2
Iv
>0
,Iv
--
p4
t3
Iv
==
2,
R
p1
2
Iv
p5
t4
M
U
L_
AD
D
p
6
t5
M
O
D
_D
IV
t7
Iv
==
1,
L
p8
t8
M
U
L_
AD
D
p9
t9
M
O
D
_D
IV
p1
5 X
p1
4
sT
L
p1
6 sT
R
p1
7
rX
p1
3
rX
p2
0 X
p1
9
sT
R
p2
1 sT
L
p2
2
rX
p1
8
rX
p7
t1
0
Iv
==
0,
H
Ри
с.
4
. И
нг
иб
ит
ор
на
я
се
ть
П
ет
ри
IP
N
TM
, и
сп
ол
ня
ю
щ
ая
м
аш
ин
у
Ть
ю
ри
нг
а,
г
де
в
—
D
A
_I
, г
—
E
X
EC
_I
(П
ро
до
лж
ен
ие
р
ис
. 4
)
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 39
Сеть EXEC_I реализует последовательно правила (г)–(е): она присваи-
вает новое значение текущему символу ленты Jxx = ; осуществляет пере-
мещение Iv головки в соответствии с принципами шифрования ленты (5)
посредством операций MUL_ADD и MOD_DIV в требуемой последователь-
ности и не изменяет значения в случае 0=vI . Затем она переключается
в следующее состояние .Jqq =
Итак, работа IPNTM полностью соответствует правилам работы МТ и
способу кодирования МТ ингибиторной сетью Петри. Когда IPNTM оста-
навливается корректно ),0( =noi шифр результата (рабочей зоны ленты)
содержится в позициях .,, sRxsL В соответствии с обычными соглашения-
ми машина останавливается в позиции управляющей головки над крайним
левым символом рабочей зоны, следовательно, 0=sL и результат считы-
вается из позиций sRx, .
В описанном способе шифрования МТ имеется лишь незначительное
отличие между детерминированной и недетерминированной МТ, которое
состоит в том, что недетерминированная МТ может содержать несколько
команд с совпадающей парой ).,( xq При нахождении подходящей команды
следует применить недетерминированный выбор команды из множества ко-
манд с совпадающей парой ).,( xq Для этой цели сеть FIND_I преобразована
в сеть FIND_I_ND. Сеть IPNTMND получена из сети IPNTM подстановкой
подсети FIND_I_ND вместо FIND_I (рис. 5).
Теорема 2. Сеть IPNTMND исполняет произвольную заданную неде-
терминированную машину Тьюринга.
Доказательство. Так как различие между детерминированной и неде-
терминированной МТ состоит в выборе подходящей команды, который реа-
лизован подсетью FIND_I и вследствие теоремы 1, следует доказать, что
использование подсети FIND_I_ND в сети IPNTMND вместо подсети
FIND_I обеспечивает недетерминированный выбор подходящей команды.
В соответствии со способом шифрования программы (подраздел
«Шифрование ленты») отношение P рассматривается как множество ко-
манд, представленное для шифрования как вектор в произвольном порядке.
Таким образом, следует найти все команды, содержащие одинаковую пару
),( xq и выполнить из них недетерминированный выбор.
Дальнейший процесс доказательства аналогичен доказательству теоре-
мы 1.
Заметим, что сеть IPNTMND является более общей, так как она может
исполнять как недетерминированную, так и детерминированную МТ, что
зависит от уникальности пар ),( xq множества команд программы. По-
строенные сети IPNTM и IPNTMND представлены покомпонентно в соот-
ветствии с использованными операциями и принципами работы с перемен-
ными. Определенный интерес представляет компоновка этих сетей в виде
единой ИСП и ее исполнение в среде некоторой моделирующей системы,
которая имитирует динамику срабатывания переходов.
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 40
p1
s
t1
AS
SI
G
N
p1
6
sP
p3
w
hi
le
t2 sP
1>
0
p1
7 sP
1
p4
t3
M
O
D_
DI
V
p5
t4
D
A_
I
p6
p2
0
Iq
t5
EQ
p2
2
q
p7
p2
3
c
t6
Iq
==
q
p8
t7
EQ
p2
4
Ix
p2
5 x
p9
p2
6
c
t8
t1
1
Iq
!=
q
p1
9
sI
p1
8
rX
t1
2
Ix
!=
x
t1
3 p2
7 fo
un
d
p1
1
p2
f
t1
0
t1
5
sP
1=
=0
p1
2
t2
0 !fo
un
d
t1
6 fo
un
d
t1
4
p1
3
t1
7
AS
SI
G
N
p3
0
fo
un
d
p1
4
p3
1
sI
1
p3
2
sI
t1
8
D
A_
I
p1
0
t9
AS
SI
G
N
p2
8 sI
p2
9
sI
1
p1
5
t1
9
Ри
с.
5
. Н
ед
ет
ер
ми
ни
ро
ва
нн
ы
й
вы
бо
р
по
дх
од
ящ
ей
к
ом
ан
ды
F
IN
D
_I
_N
D
Ингибиторная сеть Петри, исполняющая произвольную заданную машину Тьюринга
Системні дослідження та інформаційні технології, 2012, № 2 41
ВЫВОДЫ
В настоящей работе построена ингибиторная сеть Петри с фиксированной
структурой, которая исполняет произвольную заданную машину Тьюринга
как детерминированную, так и недетерминированную.
Композиция ингибиторной сети, исполняющей машину Тьюринга,
и машины Тьюринга, исполняющей ингибиторную сеть Петри, дает новый
способ представления универсальной ингибиторной сети [5], которая ис-
полняет произвольную заданную ингибиторную сеть Петри.
Возможны построения аналогичных сетей в других классах сетей Пет-
ри, которые являются универсальной алгоритмической системой [2]: при-
оритетных, синхронных, временных сетях Петри.
Известны примеры построения универсальной машины Тьюринга
с минимальным числом использованных символов/состояний [11, 12]. В этой
связи определенный интерес представляет построение сети с минимальным
количеством позиций (переходов), минимальным значением маркировки.
ЛИТЕРАТУРА
1. Agerwala T.A. Complete Model for Representing the Coordination of Asynchronous
Processes. — Baltimore: John Hopkins University, Hopkins Computer Science
Program, Res. Rep., July — № 32. — 1974. — 87 р.
2. Котов В.Е. Сети Петри. — М.: Наука, 1984. — 160 с.
3. Turing A.M. On Computable Numbers with an Application to the Entscheidung-
sproblem // Proceedings of the London Mathematical Society. — 1936. — 42. —
Р. 230–265.
4. Hopcroft J.E., Motwani R., Ullman J.D. Introduction to automata theory, languages,
and computation, second edition. — NY: Addison-Wesley, 2001. — 498 p.
5. Zaitsev D.A. Universal Inhibitor Petri Net // Proceedings of the 17-th German Work-
shop on Algorithms and Tools for Petri Nets, 7–8 October. — Cottbus,
Germany. — 2010. — P. 1–15. — http://ceur-ws.org/Vol-643/.
6. The Universal Turing Machine. A Half-Century Survey / Rolf Herken (ed.). —
Springer-Verlag, Wien New York. — 1994. — 609 p.
7. Best E., Devillers R., Koutny Petri Nets M. Process Algebra and Concurrent Pro-
gramming Languages // Lecture Notes in Computer Science. — 1492: Lectures
on Petri Nets II: Applications / Reisig W.; Rozenberg G. (eds.). — 1998. —
P. 157–198.
8. Goltz U. On Representing CCS Programs by Finite Petri Nets // Lecture Notes in
Computer Science: Proc. MFCS. — 1988. — 324. — P. 339–350.
9. Слепцов А.И. Уравнения состояний и эквивалентные преобразования нагру-
женных сетей Петри (алгебраический подход) // Формальные модели па-
раллельных вычислений: докл. и сообщ. Всесоюзн. конф. — Новоси-
бирск. — 1988. — C. 151–158.
10. Слепцов А.И., Юрасов А.А. Автоматизация проектирования управляющих сис-
тем гибких автоматизированных производств / Под ред. Б.Н. Мали-
новского. — К.: Технiка, 1986. — 160 с.
11. Minsky M. Size and structure of universal Turing machines using tag systems // Re-
cursive Function Theory, Symposium in Pure Mathematics, AMS. — 1962. —
5. — Р. 229–238.
12. Rogozhin Y. Small universal Turing machines // Theoretical Computer Science. —
1996. — 168, № 2. — Р. 215–240.
Поступила 29.07.2010
|