IJPAM: Volume 109, No. 3 (2016)


Zvi Retchkiman Königsberg
Instituto Politecnico Nacional, CIC
Mineria 17-2, Col. Escandon, Mexico D.F 11800, MEXICO

Abstract. This paper gives a proof of the normal form theorem for arithmetical Petri nets $(APN)$. The normal form theorem was introduced by Kleene for the general recursive computation paradigm in terms of system of equations. $APN$ are inhibitor Petri nets that perform three types of arithmetical operations; increment, decrement and test for zero. The proof 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.

Received: May 11, 2016

Revised: July 22, 2016

Published: October 1, 2016

AMS Subject Classification: 03D78, 03D60, 03D20, 03D10

Key Words and Phrases: normal form theorem, Petri nets, inhibitor arcs, arithmetical Petri nets, arithmetization, recursive functions, computation tree
Download paper from here.


S. Kleene, Introduction to Metamathematics, Noth Holland Publishing Co, Amsterdam, Groningen (1952),

J.C. Shepardson and H.E. Sturgis, Computability of recursive functions, Journal of the ACM, 10, No. 2 (1963), 217-255, doi: 10.1145/321160.321170.

J.L. Peterson, Petri Net Theory and The Modelling of Systems, Prentice Hall (1981).

P. Odifreddi, Recursion Theory, The Theory of Functions and Sets of Natural Numbers, Studies in Logic and the Foundations of Mathematics, Elsevier (1999).

M. Davis, R. Sigal and E. Weyuker, Computability, Complexity, and Languages, Fundamentals of Theoretical Computer Science, Academic Press (1983).

M. Davis, Computability and Unsolvability, McGraw-Hill (1958).


DOI: 10.12732/ijpam.v109i3.3 How to cite this paper?

International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 109
Issue: 3
Pages: 511 - 528

Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).