| Resumen |
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. © 2016 Zvi Retchkiman Königsberg. |
