Associating Functions and the Operator of Conditioned Iteration (Russian)
B. Buchberger
Communications of the Joint Institute for Nuclear Research, Dubna, Soviet Union,
No P5-5788, May 1971, 19 pages.
ABSTRACT:
We introduce associating functions by two axioms that characterize the behavior
of random access memories. We also define the operator of conditioned iteration
that combines two functions by iterating the first function until the second one
decides for termination.
We then show the following representation theorem: Every partial recursive function
can be obtained from constants, projections, and associating functions by composition
and just one conditioned iteration. This representation theorem appears to be more
natural than the representation theorem based on the mu-operator. We interpret the
result in terms of operational semantics for programming languages and show that
every Goedel numbering can be decomposed into a recursive input coding, a partial
recursive function that results from two recursive functions by conditioned iteration,
and a recursive output coding.
Also we give a concrete example of associating functions that, basically, uses the
representation of tuples of natural numbers as products of prime powers.