Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Theory of Computation
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/

Lecture 11: Models of Computation

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation I

Looking roughly 100 years back, mathematics faced the
problem that there have been problems for which nobody
could find an algorithm solving them.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation I

Looking roughly 100 years back, mathematics faced the
problem that there have been problems for which nobody
could find an algorithm solving them.
One of the famous examples is Hilbert’s tenth problem,
formulated as
Design an algorithm deciding whether a given Diophantine equation
has an integral solution.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation II

Finally, the idea emerged that there may be problems whichcannot be solved algorithmically.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation II

Finally, the idea emerged that there may be problems whichcannot be solved algorithmically.
Let us first see, how this idea could emerge. As a matter of fact,
without Cantor’s work, it would have been much moredifficult.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation III
Looking at all the algorithms we know, we can say that analgorithm is a computation method having the following
properties.
(1) The instruction is a finite text.
(2) The computation is done step by step, where each step
performs an elementary operation.
(3) In each step of the execution of the computation it isuniquely determined which elementary operation we haveto perform.
(4) The next computation step depends only on the input andthe intermediate results computed so far.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation III
Looking at all the algorithms we know, we can say that analgorithm is a computation method having the following
properties.
(1) The instruction is a finite text.
(2) The computation is done step by step, where each step
performs an elementary operation.
(3) In each step of the execution of the computation it isuniquely determined which elementary operation we haveto perform.
(4) The next computation step depends only on the input andthe intermediate results computed so far.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation III
Looking at all the algorithms we know, we can say that analgorithm is a computation method having the following
properties.
(1) The instruction is a finite text.
(2) The computation is done step by step, where each step
performs an elementary operation.
(3) In each step of the execution of the computation it isuniquely determined which elementary operation we haveto perform.
(4) The next computation step depends only on the input andthe intermediate results computed so far.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation III
Looking at all the algorithms we know, we can say that analgorithm is a computation method having the following
properties.
(1) The instruction is a finite text.
(2) The computation is done step by step, where each step
performs an elementary operation.
(3) In each step of the execution of the computation it isuniquely determined which elementary operation we haveto perform.
(4) The next computation step depends only on the input andthe intermediate results computed so far.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation III
Looking at all the algorithms we know, we can say that analgorithm is a computation method having the following
properties.
(1) The instruction is a finite text.
(2) The computation is done step by step, where each step
performs an elementary operation.
(3) In each step of the execution of the computation it isuniquely determined which elementary operation we haveto perform.
(4) The next computation step depends only on the input andthe intermediate results computed so far.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation IV
Now, we can also assume that there is a finite alphabet Σ suchthat every algorithm can be represented as a string from Σ∗ .
Since the number of all strings from Σ∗ is countably infinite there
are at most countably infinite many algorithms.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation IV
Now, we can also assume that there is a finite alphabet Σ suchthat every algorithm can be represented as a string from Σ∗ .
Since the number of all strings from Σ∗ is countably infinite there
are at most countably infinite many algorithms.
Recalling Cantor’s famous result that{f | f : N → {0, 1}}
is uncountably infinite, we directly arrive at the following
theorem.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation IV
Now, we can also assume that there is a finite alphabet Σ suchthat every algorithm can be represented as a string from Σ∗ .
Since the number of all strings from Σ∗ is countably infinite there
are at most countably infinite many algorithms.
Recalling Cantor’s famous result that{f | f : N → {0, 1}}
is uncountably infinite, we directly arrive at the following
theorem.
Theorem 1
There exists a noncomputable function f : N → {0, 1}.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation V
While this result is of fundamental epistemological importance,
it is telling nothing about any particular function. For
achieving results in this regard, we have to do much more.
Thus, modern computation theory starts with the question
Which problems can be solved algorithmically ?

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation V
While this result is of fundamental epistemological importance,
it is telling nothing about any particular function. For
achieving results in this regard, we have to do much more.
Thus, modern computation theory starts with the question
Which problems can be solved algorithmically ?
In order to answer it, first of all, the intuitive notion of analgorithm has to be formalized mathematically.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Motivation V
While this result is of fundamental epistemological importance,
it is telling nothing about any particular function. For
achieving results in this regard, we have to do much more.
Thus, modern computation theory starts with the question
Which problems can be solved algorithmically ?
In order to answer it, first of all, the intuitive notion of analgorithm has to be formalized mathematically.
Within this course, we shall study Gödel’s and Turing’s
formalization; i.e., partial recursive functions and Turingmachines, respectively.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions I
For all n ∈ N+ we write Pn to denote the set of all partial
recursive functions from Nn into N. Here we define N1 = N
and Nn+1 = Nn × N, i.e., Nn is the set of all ordered n-tuplesof natural numbers.
Gödel’s idea to define the set P of all partial recursive functions
is as follows:
Step (1): Define some basic functions which are intuitively
computable.
Step (2): Define some rules that can be used to construct
new computable functions from functions that are
already known to be computable.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions I
For all n ∈ N+ we write Pn to denote the set of all partial
recursive functions from Nn into N. Here we define N1 = N
and Nn+1 = Nn × N, i.e., Nn is the set of all ordered n-tuplesof natural numbers.
Gödel’s idea to define the set P of all partial recursive functions
is as follows:
Step (1): Define some basic functions which are intuitively
computable.
Step (2): Define some rules that can be used to construct
new computable functions from functions that are
already known to be computable.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions I
For all n ∈ N+ we write Pn to denote the set of all partial
recursive functions from Nn into N. Here we define N1 = N
and Nn+1 = Nn × N, i.e., Nn is the set of all ordered n-tuplesof natural numbers.
Gödel’s idea to define the set P of all partial recursive functions
is as follows:
Step (1): Define some basic functions which are intuitively
computable.
Step (2): Define some rules that can be used to construct
new computable functions from functions that are
already known to be computable.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions II
In order to complete Step (1), we define the following functions
Z, S, V : N → N by setting:Z(n) =df 0

for all n ∈ N,

S(n) =df n + 1 for all n ∈ N,0,
if n = 0 ;V(n) =dfn − 1, for all n > 1 .
That is, Z is the constant 0 function, S is the successor function
and V is the predecessor function. Clearly, these functions are
intuitively computable. Therefore, by definition we have
Z, S, V ∈ P1 . This completes Step (1) of the outline given
above.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions III
Next, we define the rules (cf. Step (2)).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions III
Next, we define the rules (cf. Step (2)).
(2.1) (Introduction of fictitious variables)
Let n ∈ N+ ; then we have: if τ ∈ Pn andψ(x1 , . . . , xn , xn+1 ) =df τ(x1 , . . . , xn ), then ψ ∈ Pn+1 .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions III
Next, we define the rules (cf. Step (2)).
(2.1) (Introduction of fictitious variables)
Let n ∈ N+ ; then we have: if τ ∈ Pn andψ(x1 , . . . , xn , xn+1 ) =df τ(x1 , . . . , xn ), then ψ ∈ Pn+1 .
(2.2) (Identifying variables)
Let n ∈ N+ ; then we have: if τ ∈ Pn+1 andψ(x1 , . . . , xn ) =df τ(x1 , . . . , xn , xn ), then ψ ∈ Pn .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions III
Next, we define the rules (cf. Step (2)).
(2.1) (Introduction of fictitious variables)
Let n ∈ N+ ; then we have: if τ ∈ Pn andψ(x1 , . . . , xn , xn+1 ) =df τ(x1 , . . . , xn ), then ψ ∈ Pn+1 .
(2.2) (Identifying variables)
Let n ∈ N+ ; then we have: if τ ∈ Pn+1 andψ(x1 , . . . , xn ) =df τ(x1 , . . . , xn , xn ), then ψ ∈ Pn .
(2.3) (Permuting variables) Let n ∈ N+ , n > 2 and leti ∈ {1, . . . , n}; then we have: if τ ∈ Pn andψ(x1 , . . . , xi , xi+1 , . . . , xn ) =df τ(x1 , . . . , xi+1 , xi , . . . , xn ),then ψ ∈ Pn .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions IV(2.4) (Composition)
Let n ∈ N and m ∈ N+ . Furthermore, let τ ∈ Pn+1 , letψ ∈ Pm and defineφ(x1 , . . . , xn , y1 , . . . , ym ) =df τ(x1 , . . . , xn , ψ(y1 , . . . , ym )).
Then φ ∈ Pn+m .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions IV(2.4) (Composition)
Let n ∈ N and m ∈ N+ . Furthermore, let τ ∈ Pn+1 , letψ ∈ Pm and defineφ(x1 , . . . , xn , y1 , . . . , ym ) =df τ(x1 , . . . , xn , ψ(y1 , . . . , ym )).
Then φ ∈ Pn+m .
(2.5) (Primitive recursion)
Let n ∈ N, let τ ∈ Pn and let ψ ∈ Pn+2 . Then we have: if
φ(x1 , . . . , xn , 0) =df τ(x1 , . . . , xn );φ(x1 , . . . , xn , y + 1) =df ψ(x1 , . . . , xn , y, φ(x1 , . . . , xn , y)) ,then φ ∈ Pn+1 .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions V(2.6) (µ-recursion)
Let n ∈ N+ ; then we have: if τ ∈ Pn+1 andψ(x1 , . . . , xn ) =df µy[τ(x1 , . . . , xn , y) = 1]
the smallest y such that
(1) τ(x1 , . . . , xn , v) is defined for all v 6 y;
=df (2) τ(x1 , . . . , xn , v) , 1 for all v < y;(3) τ(x1 , . . . , xn , y) = 1 ,if such a y exists;
not defined ,otherwise ;then ψ ∈ Pn .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem I

Note that all operations given above except Operation (2.5) are
explicit. Operation (2.5) itself constitutes an implicit definition,
since φ appears on both the left and right hand side. Thus,
before we can continue, we need to verify whether or not
Operation (2.5) does always defines a function. This is by nomeans obvious. Recall that every implicit definition needs ajustification.
Therefore, we have to show the following theorem:

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem II

Theorem 2
If τ and ψ are functions, then there is precisely one function φsatisfying the scheme given in Operation (2.5).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem II

Theorem 2
If τ and ψ are functions, then there is precisely one function φsatisfying the scheme given in Operation (2.5).
Proof. We have to show uniqueness and existence of φ.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem III
Claim 1. There is at most one function φ satisfying the scheme given
in Operation (2.5).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem III
Claim 1. There is at most one function φ satisfying the scheme given
in Operation (2.5).
Suppose there are functions φ1 and φ2 satisfying the scheme
given in Operation (2.5). We show by induction over y that
φ1 (x1 , . . . , xn , y) = φ2 (x1 , . . . , xn , y) for all x1 , . . . , xn , y ∈ N .
For the induction basis, let y = 0. Then we directly get for all
x1 , . . . , xn ∈ N
φ1 (x1 , . . . , xn , 0) = τ(x1 , . . . , xn )= φ2 (x1 , . . . , xn , 0) .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem IV
Now, we assume as induction hypothesis (abbr. IH) that for all
x1 , . . . , xn ∈ N and some y ∈ N
φ1 (x1 , . . . , xn , y) = φ2 (x1 , . . . , xn , y) .
The induction step is done from y to y + 1. Using the scheme
provided in Operation (2.5) we obtain
φ1 (x1 , . . . , xn , y + 1) = ψ(x1 , . . . , xn , y, φ1 (x1 , . . . , xn , y))by def.
= ψ(x1 , . . . , xn , y, φ2 (x1 , . . . , xn , y))by the IH= φ2 (x1 , . . . , xn , y + 1)

by def. .

Consequently φ1 = φ2 , and Claim 1 is proved.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem V
Claim 2. There is a function φ satisfying the scheme given in
Operation (2.5).
For showing the existence of φ we replace the inductive andimplicit definition of φ by an infinite sequence of explicit
definitions; i.e., let
φ0 (x1 , . . . , xn , y) =df

τ(x1 , . . . , xn ), if y = 0 ;not defined, otherwise .


if y < 1 ; φ0 (x1 , . . . , xn , y),φ1 (x1 , . . . , xn , y) =df ψ(x1 , . . . , xn , 0, φ0 (x1 , . . . , xn , 0)), if y = 1 ;not defined,
otherwise .
...

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem VI
if y < i + 1 ; φi (x1 , . . . , xn , y),φi+1 (x1 , . . . , xn , y) =df ψ(x1 , . . . , xn , i, φi (x1 , . . . , xn , i)), if y = i + 1 ;
not defined,
otherwise .
...

All definitions of the functions φi are explicit, and thus thefunctions φi exist by the set forming axiom. Consequently, fory ∈ N and every x1 , . . . , xn ∈ N the function φ defined byφ(x1 , . . . , xn , y) =df φy (x1 , . . . , xn , y)does exist.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Dedekind’s Justification Theorem VII

Furthermore, by construction we directly get
φ(x1 , . . . , xn , 0) = φ0 (x1 , . . . , xn , 0)
= τ(x1 , . . . , xn )andφ(x1 , . . . , xn , y + 1) = φy+1 (x1 , . . . , xn , y + 1)
= ψ(x1 , . . . , xn , y, φy (x1 , . . . , xn , y))= ψ(x1 , . . . , xn , y, φ(x1 , . . . , xn , y)) ,and thus, φ is satisfying the scheme given in Operation (2.5).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions VI
Definition 1
We define the class P of all partial recursive functions to be thesmallest function class containing the functions Z, S and V andall functions that can be obtained from Z, S and V by finitely
many applications of the Operations (2.1) through (2.6).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Defining Partial Recursive Functions VI
Definition 1
We define the class P of all partial recursive functions to be thesmallest function class containing the functions Z, S and V andall functions that can be obtained from Z, S and V by finitely
many applications of the Operations (2.1) through (2.6).
Furthermore, we define the important subclass of primitive
recursive functions as follows.
Definition 2
We define the class Prim of all primitive recursive functions tobe the smallest function class containing the functions Z, S and
V and all functions that can be obtained from Z, S and V byfinitely many applications of the Operations (2.1) through (2.5).
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Example 1 (Identity Function)
The identity function I : N → N defined by I(x) = x for all x ∈ N is
primitive recursive.
Proof. We want to apply Operation (2.4). Let n = 0 and m = 1.
By our definition (cf. Step (1)), we know that V, S ∈ P1 . So, V
serves as the τ (note that n + 1 = 0 + 1 = 1) and S serves as
the ψ in Operation (2.4) (note that m = 1). Consequently, thedesired function I is the φ in Operation (2.4)(note that n + m = 0 + 1 = 1) and we can set
I(x) =df V(S(x)) .
Hence, the identity function I is primitive recursive.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Example 2 (Binary Addition)
The binary addition function α : N × N → N given byα(n, m) = n + m for all n, m ∈ N is is primitive recursive.
Proof. By assumption, S ∈ P. As shown in Example 1, I ∈ Prim.
First, we define some auxiliary functions by using theoperations indicated below.
ψ(x1 , x2 ) =df S(x1 )by using Operation (2.1);ψ̃(x1 , x2 ) =df ψ(x2 , x1 )by using Operation (2.3);

τ(x1 , x2 , x3 ) =df ψ̃(x1 , x2 )by using Operation (2.1);τ̃(x1 , x2 , x3 ) =df τ(x1 , x3 , x2 )by using Operation (2.3) .

Now, we apply Operation (2.5) for defining α, i.e., we setα(n, 0) =df I(n),α(n, m + 1) =df τ̃(n, m, α(n, m)) .
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Binary Addition II
Since we only used Operations (2.1) through (2.5), we see thatα ∈ Prim.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Binary Addition II
Since we only used Operations (2.1) through (2.5), we see thatα ∈ Prim.
So, let us compute α(n, 1). Then we getα(n, 1) = α(n, 0 + 1) = τ̃(n, 0, α(n, 0))= τ̃(n, 0, I(n)) by using α(n, 0) = I(n) ,= τ̃(n, 0, n) by using I(n) = n ,= τ(n, n, 0) by using the definition of τ̃ ,= ψ̃(n, n) by using the definition of τ ,= ψ(n, n)

by using the definition of ψ̃ ,= S(n) = n + 1

Theory of Computationby using the definition of ψ and S .

c Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Binary Addition III

So, our definition may look more complex than necessary. In
order to see, it is not, we compute α(n, 2).
α(n, 2) = α(n, 1 + 1) = τ̃(n, 1, α(n, 1))= τ̃(n, 1, n + 1) by using α(n, 1) = n + 1 ,= τ(n, n + 1, 1)= ψ̃(n, n + 1)
= ψ(n + 1, n)= S(n + 1) = n + 2 .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Binary Multiplication
In the following we shall often omit some of the tedioustechnical steps. For example, in order to clarify that binary
multiplication is primitive recursive, we simply point out thatis suffices to setm(x, 0) = Z(x) ,m(x, y + 1) = α(x, m(x, y)) .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Binary Multiplication
In the following we shall often omit some of the tedioustechnical steps. For example, in order to clarify that binary
multiplication is primitive recursive, we simply point out thatis suffices to setm(x, 0) = Z(x) ,m(x, y + 1) = α(x, m(x, y)) .
Also note that the constant 1 function c is primitive recursive;i.e., c(n) = 1 for all n ∈ N. For seeing this, we set
c(0) = S(0) ,c(n + 1) = c(n) .
In the following, instead of c(n) we just write 1.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Signum and Arithmetic Difference
Now, it is easy to see that the signum function sg is primitive
recursive, since we havesg(0) = 0 ,sg(n + 1) = 1 .

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Signum and Arithmetic Difference
Now, it is easy to see that the signum function sg is primitive
recursive, since we havesg(0) = 0 ,sg(n + 1) = 1 .
Since the natural numbers are not closed under subtraction, one
conventionally uses the so-called arithmetic difference defined. n = m − n if m > n and 0 otherwise. The arithmetic
as m −
difference is primitive recursive, too, since for all n, m ∈ N wehave
. 0 = I(m) ,m−. (n + 1) = V(m −. n) .
m−
Generalizations of the examples given so far are in the book.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions I
Quite often one is defining functions by making case distinctions (cf., e.g., our definition of the predecessor function V).
So, it is only natural to ask under what circumstances
definitions by case distinctions do preserve primitive
recursiveness. A convenient way to describe properties is theusage of predicates. An n-ary predicate p over the natural
numbers is a subset of Nn . Usually, one writes p(x1 , . . . , xn )instead of (x1 , . . . , xn ) ∈ p. The characteristic function of n-ary
predicate p is the function χp : Nn → {0, 1} defined byχp (x1 , . . . , xn ) =Theory of Computation

1,0,

if p(x1 , . . . , xn ) ;otherwise .

c Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions II

Definition 3
A predicate p is said to be primitive recursive if χp is primitive
recursive.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions II

Definition 3
A predicate p is said to be primitive recursive if χp is primitive
recursive.

Definition 4
Let p, q be n-ary predicates, then we define p ∧ q to be the set
p ∩ q, p ∨ q to be the set p ∪ q, and ¬p to be the set Nn \ p.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions III
Lemma 3
Let p, q be any primitive recursive n-ary predicates. Then p ∧ q,
p ∨ q, and ¬p are also primitive recursive.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions III
Lemma 3
Let p, q be any primitive recursive n-ary predicates. Then p ∧ q,
p ∨ q, and ¬p are also primitive recursive.
Proof. Obviously, it holds
χp∧q (x1 , . . . , xn ) = χp (x1 , . . . , xn ) · χq (x1 , . . . , xn ) ,χp∨q (x1 , . . . , xn ) = sg(χp (x1 , . . . , xn ) + χq (x1 , . . . , xn )) ,. χ (x , . . . , x ) .
χ (x , . . . , x ) = 1 −
¬p

1

n

p

1

n

Since we already know addition, multiplication and thearithmetic difference to be primitive recursive, the assertion of
the lemma follows.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions IV
Now, we can show our theorem concerning function definitions
by making case distinctions.
Theorem 4
Let p1 , . . . , pk be pairwise disjoint n-ary primitive recursive
predicates, and let ψ1 , . . . , ψk ∈ Pn be primitive recursive functions.
Then the function γ : Nn → N defined byψ1 (x1 , . . . , xn ),if p1 (x1 , . . . , xn ) ;


 ·




·
γ(x1 , . . . , xn ) =df
·





ψ (x , . . . , xn ),if pk (x1 , . . . , xn ) ;

 k 1
0,
otherwise ;is primitive recursive.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Case Distinctions V

Proof. Since we can write γ as
γ(x1 , . . . , xn ) =kXχpi (x1 , . . . , xn ) · ψi (x1 , . . . , xn ) ,i=1

the theorem follows from the primitive recursiveness of general
addition and multiplication.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions I

Quite often it would be very useful to have a bijection from
N × N to N. So, first we have to ask whether or not such abijection does exist.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions I

Quite often it would be very useful to have a bijection from
N × N to N. So, first we have to ask whether or not such abijection does exist.
This is indeed the case.
Recall that the elements of N × N are ordered pairs of natural
numbers. So, we may easily represent all elements of N × N ina two dimensional array, where row x contains all pairs (x, y),i.e., having x in the first component and y = 0, 1, 2, . . .
(cf. Figure 1).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions II(0, 0)(1, 0)(2, 0)(3, 0)(4, 0)(5, 0)...

(0, 1)(1, 1)(2, 1)(3, 1)(4, 1)...
...

(0, 2)(1, 2)(2, 2)(3, 2)(4, 2)(0, 3)(1, 3)(2, 3)(3, 3)(4, 3)(0, 4)(1, 4)(2, 4)(3, 4)(4, 4)

...
...
...
...
...

Figure 1: A two dimensional array representing N × N.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions III
Now, the idea is to arrange all these pairs in a sequence starting(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1), (3, 0), . . .

(1)In this order, all pairs (x, y) appear before all pairs (x 0 , y 0 ) if andonly if x + y < x 0 + y 0 . That is, they are arranged in order ofincrementally growing component sums. The pairs with thesame component sum are ordered by the first component
starting with the smallest one. That is, pair (x, y) is located in
the segment(0, x + y), (1, x + y − 1), . . . , (x, y), . . . , (x + y, 0) .
Note that there are x + y + 1 many pairs having the component
sum x + y. Thus, in front of pair (0, x + y) we have in the
Sequence (1) x + y many segments containing a total of
1 + 2 + 3 + · · · + (x + y)
many pairs.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions IV
Taking into account that
n
X
i=0

X
n(n + 1)
i =
i
=
2
n

i=1

we thus can define the desired bijection c : N × N → N bysettingc(x, y) ==Theory of Computation(x + y)(x + y + 1)+x
2(x + y)2 + 3x + y
.
2

(2)

c Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions V

All the operations involved in computing c have already beenshown to be primitive recursive, thus we can conclude that c isprimitive recursive, too.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions V

All the operations involved in computing c have already beenshown to be primitive recursive, thus we can conclude that c isprimitive recursive, too.
Exercise. Determine the functions d1 and d2 such that for all
x, y ∈ N, if z = c(x, y) then x = d1 (z) and y = d2 (z).

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions V

All the operations involved in computing c have already beenshown to be primitive recursive, thus we can conclude that c isprimitive recursive, too.
Exercise. Determine the functions d1 and d2 such that for all
x, y ∈ N, if z = c(x, y) then x = d1 (z) and y = d2 (z).
Exercise. Show that for every fixed k ∈ N, k > 2, there is aprimitive recursive bijection ck : Nk → N.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Pairing Functions V

All the operations involved in computing c have already beenshown to be primitive recursive, thus we can conclude that c isprimitive recursive, too.
Exercise. Determine the functions d1 and d2 such that for all
x, y ∈ N, if z = c(x, y) then x = d1 (z) and y = d2 (z).
Exercise. Show that for every fixed k ∈ N, k > 2, there is aprimitive recursive bijection ck : Nk → N.
Exercise. Let N∗ be the set of all finite sequences of natural numbers.
Show that there is a primitive recursive bijection c∗ : N∗ → N.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

General Recursive Functions
Next, we define the class of general recursive functions.
Definition 5
For all n ∈ N+ we define Rn to be the set of all functionsf ∈ Pn such that f(x1 , . . . , Sxn ) is defined for all x1 , . . . , xn ∈ N.
Furthermore, we set R = n∈N+ Rn .
In other words, R is the set of all functions that are total andpartial recursive. Now, we can show the following theorem:

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

General Recursive Functions
Next, we define the class of general recursive functions.
Definition 5
For all n ∈ N+ we define Rn to be the set of all functionsf ∈ Pn such that f(x1 , . . . , Sxn ) is defined for all x1 , . . . , xn ∈ N.
Furthermore, we set R = n∈N+ Rn .
In other words, R is the set of all functions that are total andpartial recursive. Now, we can show the following theorem:
Theorem 5
Prim ⊂ R ⊂ P.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof I
Proof. Clearly Z, S, V ∈ R. Furthermore, after a bit of reflection
it should be obvious that any finite number of applications ofOperations (2.1) through (2.5) results only in total functions.
This shows Prim ⊆ R.
Also, R ⊆ P is obvious by definition. So, it remains to showthat the two inclusions are proper.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof I
Proof. Clearly Z, S, V ∈ R. Furthermore, after a bit of reflection
it should be obvious that any finite number of applications ofOperations (2.1) through (2.5) results only in total functions.
This shows Prim ⊆ R.
Also, R ⊆ P is obvious by definition. So, it remains to showthat the two inclusions are proper.
Claim 1. P \ R , ∅.
By definition, S ∈ P and using Operation (2.4) it is easy to seethat δ(n) =df S(S(n)) is in P, too. Now, note that
δ(n) = n + 2 > 1 for all n ∈ N.
Using Operation (2.1) we define τ(x, y) = δ(y), and thus τ ∈ P.
Consequently,
ψ(x) = µy[τ(x, y) = 1]
is the nowhere defined function and hence ψ < R. On the other
hand, by construction ψ ∈ P. Therefore, we get ψ ∈ P \ R.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof II
Claim 2. R \ Prim , ∅.
Showing this claim is much more complicated. First, we define
a function
ap(0, m) =df m + 1 ,ap(n + 1, 0) =df ap(n, 1) ,ap(n + 1, m + 1) =df ap(n, ap(n + 1, m)) ,which is the so-called Ackermann-Péter function. Hilbert
conjectured in 1926 that every total and computable function is
also primitive recursive. This conjecture was disproved byAckermann in 1928 and Péter simplified Ackermann’s
definition in 1955.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof III

Now, it suffices to show that function ap is not primitive
recursive and that function ap is general recursive. Both parts
are not easy to prove. So, due to the lack of time, we must skip
some parts. But before we start, let us confine ourselves that thefunction ap is intuitively computable. For doing this, consider
the following fragment of pseudo-code implementing thefunction ap as peter.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof IV

function peter(n, m)
if n = 0
return m + 1
else if m = 0
return peter(n - 1, 1)
else
return peter(n - 1, peter(n, m - 1))

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof V
Next, we sketch the proof that ap cannot be primitive recursive.
First, for every primitive recursive function φ, one defines afunction fφ as follows. Let k be the arity of φ; then we setfφ (n) = max φ(x1 , . . . , xk ) |kXxi 6 n.

i=1Then, by using the inductive construction of the class Prim, one
can show by structural induction that for every primitive
recursive function φ there is a number nφ ∈ N such thatfφ (n) < ap(nφ , n)

for all n > nφ .

Intuitively, the latter statement shows that the AckermannPéter function grows faster than every primitive recursivefunction.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof VI
The rest is then easy. Suppose ap ∈ Prim. Then, taking into
account that the identity function I is primitive recursive, one
directly sees by application of Operation (2.4) that
κ(n) = ap(I(n), I(n))
is primitive recursive, too. Now, for κ there is a number nκ ∈ Nsuch thatfκ (n) < ap(nκ , n) for all n > nκ .
But now,κ(nκ ) 6 fκ (nκ ) < ap(nκ , nκ ) = κ(nκ ) ,a contradiction.
Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Proof VII

For the second part, one has to prove that ap ∈ R which mainlymeans to provide a construction to express the function ap
using the Operations (2.1) through (2.5) and the µ-operator. We
refer the interested reader to Hermes.

Theory of Computationc Thomas Zeugmann

Motivation

Partial Recursive Functions

ExamplesPairing

General Recursive Functions

End

Thank you!

Theory of Computationc Thomas Zeugmann