TY - JOUR
T1 - Computability equivalence of an extended Petri net model
AU - Königsberg, Zvi Retchkiman
N1 - Publisher Copyright:
© 2016 Zvi Retchkiman Königsberg.
PY - 2016
Y1 - 2016
N2 - The notion of computability has its origin in the works of the logicians Church, Gödel, Kleene, Post and Turing. Several approaches of computation were proposed: recursive functions, Post programs, lambda calculus, Turing machines, register machines, to mention some. It was shown that all these models were equivalent in terms of its computability power. In this paper a new computational paradigm called arithmetic Petri nets (APN) is introduced. APN are Petri nets with inhibitor arcs that perform three types of arithmetical operations; increment, decrement and test for zero. Its equivalence to Turing and therefore to all the other approaches was shown to be true by simulation of a register machine. In this paper a different path is proposed by first proving that all recursive functions are APN computable. The opposite implication is obtained from Kleene's normal form theorem for APN. The normal form theorem was introduced by Kleene for the general recursive computation paradigm in terms of system of equations. The proof of Kleene's normal form theorem for the APN computational paradigm is based on the idea of computation tree, where each node of such a tree will tell us how a value needed for the arithmetical operations can be inductively obtained. Then, using arithmetization plus course of value recursion a primitive recursive predicate is defined from which by means of a primitive recursive function the desired characterization for the value of the output function is established.
AB - The notion of computability has its origin in the works of the logicians Church, Gödel, Kleene, Post and Turing. Several approaches of computation were proposed: recursive functions, Post programs, lambda calculus, Turing machines, register machines, to mention some. It was shown that all these models were equivalent in terms of its computability power. In this paper a new computational paradigm called arithmetic Petri nets (APN) is introduced. APN are Petri nets with inhibitor arcs that perform three types of arithmetical operations; increment, decrement and test for zero. Its equivalence to Turing and therefore to all the other approaches was shown to be true by simulation of a register machine. In this paper a different path is proposed by first proving that all recursive functions are APN computable. The opposite implication is obtained from Kleene's normal form theorem for APN. The normal form theorem was introduced by Kleene for the general recursive computation paradigm in terms of system of equations. The proof of Kleene's normal form theorem for the APN computational paradigm is based on the idea of computation tree, where each node of such a tree will tell us how a value needed for the arithmetical operations can be inductively obtained. Then, using arithmetization plus course of value recursion a primitive recursive predicate is defined from which by means of a primitive recursive function the desired characterization for the value of the output function is established.
KW - Arithmeti- cal petri nets
KW - Arithmetization
KW - Com- putation tree
KW - Computability equivalence
KW - Inhibitor arcs
KW - Normal form theorem
KW - Petri nets
KW - Recursive functions
UR - http://www.scopus.com/inward/record.url?scp=84983554940&partnerID=8YFLogxK
U2 - 10.12988/ams.2016.64143
DO - 10.12988/ams.2016.64143
M3 - Artículo
SN - 1312-885X
VL - 10
SP - 2141
EP - 2156
JO - Applied Mathematical Sciences
JF - Applied Mathematical Sciences
IS - 41-44
ER -