RepliCount: A Recursive Function for Natural Number Arithmetic

ABSTRACT: We demonstrate a single recursive function, a variation of Ackermann’s Function, that represents the operations of natural number arithmetic–addition, multiplication, power, and even higher-order operations such as “tower”–in terms of only the elementary concepts of the Peano Postulates, including the successor function, its inverse, zero, and comparison for zero.

HyperOperation Function H(m,n,p):

H(m,n,0)= S(n)	for m >=0, n >= 0	[H0]	p=0	succession 
H(m,0,1)= m	for m >= 0	        [H1]	p=1     addition  			
H(m,0,2)= 0	for m >= 0	        [H2]	p=2	multiplication
H(m,0,3)= 1	for m >= 0		[H3]	p=3	exponentiation	
H(m,0,p)= 1	for m >= 0, p > 3	[H4]	p=4	tetration, p=5 pentation, etc.
H(m,n,p)= H(m, H(m,P(n),p), P(p) )	for m >= 0, n > 0, p > 3  [H5]

INTRODUCTION: In Computer Science, Ackermann’s Function is a well-known example of a simple “total computable function” that is not “primitive recursive.” While teaching recursive functions in Scheme, I had noticed that this function defines the standard arithmetic operations with a single recursive function, so I decided to code the function in Scheme as a teaching tool. This post is background on the mathematics; a future post will give the actual Scheme code. See the references at the end for a more detailed mathematical treatment.

MATH NOTATION: In order to enter mathematical formulas as text, I use the following notation:

Arithmetic operators: + - * / ^ ^^
for add, subtract, multiply, divide, power, tower.

BACKGROUND: A recursive function is a function defined in terms of itself, for at least some values of it’s arguments. For the function to be well-defined, the definition must involve a conditional on the arguments such that, for some value of the arguments, the function is defined in terms not involving the function being defined, and for all values in which the function is defined in terms of itself, it can be shown (typically by induction) that the recursion will eventually reach a form not involving the function itself.

EXAMPLES of recursive functions:

Two common examples of recursive functions are the factorial function and the Fibonacci series:

Factorial: written n!  defined by: 0! = 1; n! = n * (n-1)! for (n> 0)
Fibonacci:  F(0)=0; F(1)=1; F(n) = F(n-1) + F(n-2) for n > 1;

ACKERMANN’S FUNCTION:

Ackermann’s function is interesting in recursive function theory as a simple “total computable function” that is not “primitive recursive”.

Ackermann’s original three-argument function A(m,n,p) is defined recursively as follows for nonnegative integers m, n, and p:

A(m,n,0)= m + n	        for m >=0, n >= 0	[A1]
A(m,0,1)= 0		for m >= 0		[A2]
A(m,0,2)= 1		for m >= 0		[A3]	
A(m,0,p)= m		for m >= 0, p > 2	[A4]
A(m,n,p)= A(m, A(m,n-1,p), p-1))  for m >= 0, n > 0, p > 2  [A5]	

Ackermann’s function combines the two operands m and n using p to select the “operator”, with p=0 giving addition, p=1 giving multiplication, p=2 given exponentiation, and higher values of p giving “hyper-operations”. It can be shown that Ackermann’s function implies:

A(m,n,0) = m + n	                                                         sum of m and n
A(m,n,1) = m * n   = m + m * (n-1) = (m + (m + (m + ... (m + 0)...))) 	(n m's): product m and n
A(m,n,2) = m ^ n   = m * m ^ (n-1) = (m * (m * (m * ... (m * 1)...))) 	(n m's): m to the nth power
In general, the role of formula [A5] is to reduce an operator of some order p to a sequence of operations of the next lower order, e.g. exponentiation to multiplication, multiplication to addition.

Specifically:

 
if  [p] represents an operator of order p, 
and [q] represents the operator of the next lower order p-1,
then formula [A5] reduces:

	m [p] n 
to  
	m [q] (m [q] (m [q]... (m [q] k)...))

for n occurrences of value m and operation [q], right associative,
where   k is the boundary value for n=0.

Thus, Ackermann’s function is a formal representation of the common notion that “multiplication is repeated addition”, “exponentiation is repeated multiplication”, etc.

Now we must be careful with natural language statements such as “multiplication is repeated addition”, because natural language can be ambiguous. For example, in representing 6*3 as “repeated addition”, how many “additions” take place, 2 or 3? Are there 3 “repetitions” of 6, or only 2? Can we understand 6*1 as “repeated” additions? I will endeavor to avoid such imprecise terminology, but in any case, the mathematical formulas are precise and should be considered the authoritative definitions.

So, does Ackermann’s function also define addition as “repetition” of some operator? And how do we interpret Ackermann’s function for p > 2?

There are a couple anomalies in Ackermann’s original function that make it less useful for the study of those cases, so a related Hyper-operation Function H can be defined as follows: [see http://en.wikipedia.org/wiki/Hyperoperation]

HyperOperation Function H(m,n,p):

H(m,n,0)= S(n)	for m >=0, n >= 0	[H0]	p=0	succession
H(m,0,1)= m	for m >= 0	        [H1]	p=1	addition			
H(m,0,2)= 0	for m >= 0	        [H2]	p=2	multiplication
H(m,0,3)= 1	for m >= 0		[H3]	p=3	exponentiation	
H(m,0,p)= 1	for m >= 0, p > 3	[H4]	p=4	tetration, p=5 pentation, etc.
H(m,n,p)= H(m, H(m,P(n),p), P(p) )	for m >= 0, n > 0, p > 3  [H5]

Where:
S(n) is the Peano Successor function giving the “next” natural number after n, n>=0
P(m) is the Predecessor function, the inverse of Successor, giving the “previous” number. It will be defined rigorously below.

The changes from A to H consist of:
defining addition in terms of the Peano successor function [H1],
extending the successor function to a binary right-recursive operation (p=0) [H0],
increasing the order of A operations by 1 to introduce Successor at order 0, and
changing the boundary conditions for operations p>3 [H4]

The definiton of A contains a nominal subtraction operator in the expressions (n-1) and (p-1). Subtraction per se is not even defined by the Peano Postulates.

But recognizing that the only use of “subtraction” is to decrement a natural number by one, we can replace the nominal subtraction by the inverse of the successor function. Given S(m) = n = the “next” natural number after m, for all m >= 0, we can define:

 
  P(n) = m  such that S(m) = n, for all n > 0.
So P(n) gives the “previous” natural number to n.
Since Successor is defined to give a unique value, and given the Peano inductive postulate that guarantees the repeated composition of S generates all natural numbers, a inverse P(n) exists for all n > 0.]

This substitution has been made in the definition of H above.

H(m,n,p) defines a hierarchy of operations:
p=0	S(n)	succession: 	"next" number after n
p=1	m+n	addition:	zero or more successions				
p=2	m*n	multiplication:	zero or more additions
p=3	m^n	exponentiation:	zero or more multiplications	
p=4	m^^n	tetration:	zero or more exponentiations 
p=5 	m^^^n 	pentation:	zero or more tetrations
p>5	etc.

NOTE: in keeping with the convention that ^ is right-associative, all operators have been defined as right associative. Alternative functions could be defined with left-associative operators. Alternative boundary conditions have also been used for p>3.

For p > 3, this defines a sequence “hyper-operations,” for example:

m ^^ n,  called "tower" or tetration, defined by:

m ^^ n =   m ^ (m ^ (m ^... (m ^ 1)...))  for n m's and n ^'s (n>0), 
                                           where  m^0 = 1      (n=0)
Similarly,
m ^^^ n, called pentation, is defined by:

m ^^^ n =   m ^^ (m ^^ (m ^^... (m ^^ 1)...))  for n m's and n ^^'s (n>0), 
                                               where  m^^0 = 1      (n=0)               

And so forth for higher values of p.

Thus, the HyperOperation function is a single function that reduces the basic arithmetic operations (add, multiply, power, etc.) on natural numbers to “counting”, that is, to the Peano Successor operation and it’s inverse; and beside, it defines higher-order operations beyond exponentiation, called Hyperoperations, that can also be reduced to “counting”.

The definition of H(m,n,p) for p=0 merits further comment.

We know from the Peano Postulates that addition can be reduced to successive applications of the “successor” operator, and that, given zero, the successor operator can be used to define all natural numbers, so it should be possible to express m + n in terms of zero and the Peano Successor function.

Consider for example:

Multiplication m * n can be defined recursively in terms of addition as follows:

m * 0 = 0		(n = 0)	[M0]
m * n = m + (m * P(n))	(n > 0) [M1]

so that:

m * n = (m + (m + (m + ... ( m + 0)...)))  for n occurrences of m and +. [M2]

EXAMPLE: m=6 n=3

6*3 = 6+(6*2) = 6+(6+(6*1)) = 6+(6+(6+(6*0))) = 6+(6+(6+0))

Now m + n can be defined in terms of the recurrence:

m + 0 = m                     [S0] 
m + n = S(m) + P(n))	(n>0) [S1]

but [S1] is not in the form of [M1], so it won’t fit into the pattern [A5] of the Ackermann function.

So suppose we define addition with a recursive function in the same form as [M1] using a hypothetical lower-order operator @, as follows:

m + 0 = m,			n = 0		[S0]
m + n = m @ (m + P(n)), 	n > 0		[S1]

Example:
m + 3  = (m @ (m + 2))
	= (m @ (m @ (m + 1)))
	= (m @ (m @ (m @ (m + 0))))
	= (m @ (m @ (m @ m)))		[using [S0] m + 0 = m]

Now of course the “lower order” operator with which we wish to define addition is the Peano Successor operator.
But S is a unary operator, and @ is binary.

But suppose we define:

x @ y = S(y)

So @ is a binary extension of the unary function S, using only the right argument y of @ and ignoring the left argument x.

Continuing the example with this definition of @:

	  (m @ (m @ (m @ m)))
	= (m @ (m @ S(m)))			[using m @ m = S(m)] 
	= (m @ S(S(m)))
	= S(S(S(m)))

Now for example, let m = 6

	 
	  S(S(S(m)))
	= S(S(S(6)))
	= S(S(7))
	= S(8)	
	= 9
Thus we have computed:

6 + 3 = 9

So H “adds” 6 + 3 by performing “3 counts” from 6 to reach 9.

Thus this expresses addition (+) as zero or more applications of the Peano successor operator, within the general form of the Ackermann recurrence expression.

In a future post, I will show how this function can be programmed in the recursive function programming language Scheme.

REFERENCES:



Rubtsov, Constantin A., and Romerio, Giovanni F., (2004) “Ackermann’s Function and the New Arithmetic Operations”, http://www.rotarysaluzzo.it/filePDF/Iperoperazioni%20(1).pdf

https://en.wikipedia.org/wiki/Ackermann_function

Wilhelm Ackermann (1928). “Zum Hilbertschen Aufbau der reellen Zahlen”. Mathematische Annalen 99: 118–133. doi:10.1007/BF01459088.

http://en.wikipedia.org/wiki/Hyperoperation

http://en.wikipedia.org/wiki/Peano_axioms

http://homepages.math.uic.edu/~libgober/math215/export/215problem.pdf: proof that Peano addition is associative

About DrTechDaddy

Dr Tech Daddy is a retired computer science professor with additional interests in music, robotics, STEM education, model railroading, mathematical physics, congenital heart disease and heart transplant, and Christian theology.
This entry was posted in STEM and tagged , , , , , , , , , , , . Bookmark the permalink.