Universal Functions and Universal Programs

Application of the Universal Program

Effective Operations on Computable Functions

Universal Program∗

Xiaofeng Gao

Department of Computer Science and Engineering

Shanghai Jiao Tong University, P.R.China

CS363-Computability Theory

∗
Special thanks is given to Prof. Yuxi Fu for sharing his teaching materials.
CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 1/34
 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Outline

1 Universal Functions and Universal Programs

2 Application of the Universal Program

3 Effective Operations on Computable Functions

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 2/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Outline

1 Universal Functions and Universal Programs

2 Application of the Universal Program

3 Effective Operations on Computable Functions

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 3/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

General Remark

There are universal programs that embody all the programs.

A program is universal if upon receiving the Gödel number of a

program it simulates the program indexed by the number.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 4/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Intuition

Consider the function ψ(x, y) defined as follows

ψ(x, y) ≃ φx (y).

In an obvious sense ψ(x, _) is a universal function for the unary

funcitons
φ0 , φ1 , φ2 , φ3 , . . . .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 5/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Universal Function

The universal function for n-ary computable functions is the

(n)
(n + 1)-ary function ψU defined by
(n) (n)
ψU (e, x1 , . . . , xn ) ≃ φe (x1 , . . . , xn ).
(1)
We write ψU for ψU .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 6/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Universal Function

The universal function for n-ary computable functions is the

(n)
(n + 1)-ary function ψU defined by
(n) (n)
ψU (e, x1 , . . . , xn ) ≃ φe (x1 , . . . , xn ).
(1)
We write ψU for ψU .

(n)
Question: Is ψU computable?

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 6/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

The Theorem

(n)
Theorem. For each n, the universal function ψU is computable.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 7/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

The Theorem

(n)
Theorem. For each n, the universal function ψU is computable.

Proof. Given a number e, decode the number to get the program Pe ;

and then simulate the program Pe . If the simulation ever terminates,
(n)
then return the number in R1 . By Church-Turing Thesis, ψU is
computable.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 7/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Proof in Detail

The states of the computation of the program Pe (x) can be described

by a configuration and an instruction number.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 8/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Proof in Detail

The states of the computation of the program Pe (x) can be described

by a configuration and an instruction number.

A state can be coded up by the number

σ = π(c, j),

where c is the configuration that codes up the current values in the

registers Y r
c = 2r1 3r2 . . . = pi i ,
i≥1

and j is the next instruction number.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 8/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Step 1: Three New (n + 2)-ary functions

Define two new functions cn and jn :

cn (e, x, t) = the configuration after t steps of Pe (x),

jn (e, x, t) = the number of the next instruction after t steps
of Pe (x) (it is 0 if Pe (x) stops in t or less steps),

If the computation of Pe (x) stops, it does so in µt(jn (e, x, t) = 0)

steps, and the final configuration is cn (e, x, µt(jn (e, x, t) = 0)).
(n)
ψU (e, x) ≃ (cn (e, x, µt(jn (e, x, t) = 0)))1

Let σn (e, x, t) = π(cn (e, x, t), j n (e, x, t)). If σn is primitive

recursive, then cn , jn are primitive recursive!

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 9/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Step 2: Computability of σn(e, x, t)

The function σn can be defined by recursion as follows:

σn (e, x, 0) = π(2x1 3x2 . . . pxnn , 1),

σn (e, x, t + 1) = π(config(e, σn (e, x, t)), next(e, σn (e, x, t))),

if 1 ≤ j ≤ s

 New configuration after
 th
config(e, π(c, j)) = j instruction of P e is obeyed,


c, otherwise.

if 1 ≤ j ≤ s

 No. of next instruction after
 th
next(e, π(c, j)) = j instruction of Pe is obeyed on c, and it exists


0, otherwise.

If config and next are primitive recursive, then so is σn !

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 10/34
 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Step 3: Computability of config and next

ln(e) = the number of instructions in Pe ;


the code of Ij in Pe , if 1 ≤ j ≤ ln(e),
gn(e, j) =
0, otherwise.

ch(c, z) = the resulting configuration when the

configuration c is operated on by the
instruction with code number z.


 the number j′ of the next instruction
 when the configuration c is operated if j > 0,

v(c, j, z) = on by the jth instruction with code z,



0, if j = 0.


CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 11/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Step 3: Computability of config and next (2)

We can define the function config(_, _) by


ch(π1 (σ), gn(e, π2 (σ))), if 1 ≤ π2 (σ) ≤ ln(e),
config(e, σ) =
π1 (σ), otherwise.

and the function next(_, _) by


v(π1 (σ), π2 (σ), gn(e, π2 (σ))), if 1 ≤ π2 (σ) ≤ ln(e),
next(e, σ) =
0, otherwise.

If ln, gn, ch, and v are primitive recursive, then so are config and
next!

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 12/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Step 4: Computability of ln, gn, ch, and v

Any number x ∈ N has a unique expression as
∞
αi 2i , with αi = 0 or 1, all i.
P
(a) x =
i=0
(b) x = 2b1 + 2b2 + . . . + 2bl , with 0 ≤ b1 < b2 < ... < bl and l ≥ 1.
(c) x = 2a1 + 2a1 +a2 +1 + . . . + 2a1 +a2 +...+ak +k−1 .
Define α, ℓ, b, and a as follows:
α(i, x) =
 αi as in the expression (a);
ℓ as in (b), if x > 0,
ℓ(x) =
0 otherwise;
bi as in (b), if x > 0 and 1 ≤ i ≤ l,
b(x) =
0 otherwise;
ai as in (c), if x > 0 and 1 ≤ i ≤ l,
a(i, x) =
0 otherwise;
Each of the functions α, ℓ, b, a is computable.
CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 13/34
 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

ln and gn are primitive recursive

Both functions are primitive recursive since

ln(e) = ℓ(e + 1),

gn(e, j) = a(j, e + 1).

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 14/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Computability of ch, and v

Define primitive recursive functions u, u1 , u2 , v1 , v2 , and v3 :
u(z) = m whenever z = β(Z(m)) or z = β(S(m)):

u(z) = qt(4, z) + 1.

u1 (z) = m1 and u2 (z) = m2 whenever z = β(T(m1 , m2 )):

u1 (z) = π1 (qt(4, z)) + 1,

u2 (z) = π2 (qt(4, z)) + 1.

v1 (z) = m1 and v2 (z) = m2 and v3 (z) = q if z = β(J(m1 , m2 , q)):

v1 (z) = π1 (π1 (qt(4, z))) + 1,

v2 (z) = π2 (π1 (qt(4, z))) + 1,
v3 (z) = π2 (qt(4, z)) + 1.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 15/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Computability of ch, and v

Define primitive recursive functions zero, succ, and rans:

The change in the configuration c effected by instruction Z(m):
(c)
zero(c, m) = qt(pm m , c).

The change in the configuration c effected by instruction S(m):

succ(c, m) = pm c.

The change in the configuration c effected by instruction T(m, n):

(c) (c)m
tran(c, m, n) = qt(pn n , pn c).

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 16/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

ch, and v are primitive recursive



 zero(c, u(z)), if rm(4, z) = 0,
succ(c, u(z)), if rm(4, z) = 1,

ch(c, z) =
 tran(c, u1 (z), u2 (z)),
 if rm(4, z) = 2,
c, if rm(4, z) = 3.



 j + 1, if rm(4, z) 6= 3,
v(c, j, z) = j + 1, if rm(4, z) = 3 ∧ (c)v1 (z) =6 (c)v2 (z) ,
v3 (z), if rm(4, z) = 3 ∧ (c)v1 (z) = (c)v2 (z) .


CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 17/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Conclusion

We conclude that the functions cn , jn , σn are primitive recursive.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 18/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Further Constructions

For each n ≥ 1, the following predicates are primitive recursive:

def
1. Sn (e, x, y, t) = ‘Pe (x) ↓ y in t or fewer steps’.
def
2. Hn (e, x, t) = ‘Pe (x) ↓ in t or fewer steps’.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 19/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Further Constructions

For each n ≥ 1, the following predicates are primitive recursive:

def
1. Sn (e, x, y, t) = ‘Pe (x) ↓ y in t or fewer steps’.
def
2. Hn (e, x, t) = ‘Pe (x) ↓ in t or fewer steps’.

They are defined by

def
Sn (e, x, y, t) = jn (e, x, t) = 0 ∧ (cn (e, x, t))1 = y,
def
Hn (e, x, t) = jn (e, x, t) = 0.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 19/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Kleene’s Normal Form Theorem

Theorem. (Kleene)
There is a primitive recursive function U(x) and for each n ≥ 1 a
primitive recursive predicate Tn (e, x, z) such that
(n)
1. φe (x) is defined if and only if ∃z.Tn (e, x, z).
(n)
2. φe (x) ≃ U(µzTn (e, x, z)).

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 20/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Kleene’s Normal Form Theorem

Theorem. (Kleene)
There is a primitive recursive function U(x) and for each n ≥ 1 a
primitive recursive predicate Tn (e, x, z) such that
(n)
1. φe (x) is defined if and only if ∃z.Tn (e, x, z).
(n)
2. φe (x) ≃ U(µzTn (e, x, z)).

Proof. Let Tn (e, x, z) = Sn (e, x, (z)1 , (z)2 ). Then (1) is clear.

For (2) let U(x) = (x)1 . Then
(n)
φe (x) ≃ U(µz.Tn (e, x, z)).

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 20/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Every computable function can be obtained from a primitive recursive

function by using at most one application of the µ-operator in a
standard manner.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 21/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Outline

1 Universal Functions and Universal Programs

2 Application of the Universal Program

3 Effective Operations on Computable Functions

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 22/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Undecidability

Theorem. The problem ‘φx is total’ is undecidable.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 23/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Undecidability

Theorem. The problem ‘φx is total’ is undecidable.

Proof. If ‘φx is total’ were decidable, then by Church’s Thesis


ψU (x, x) + 1, if φx is total,
f (x) =
0, if φx is not total.

would be a total computable function that differs from every total

computable function.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 23/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Nonprimitive Total Computable Function

Theorem. There is a total computable function that is not primitive

recursive.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 24/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Nonprimitive Total Computable Function

Theorem. There is a total computable function that is not primitive

recursive.

Proof.
1. The primitive recursive functions are effectively denumerable.

2. Construct a coding of a primitive recursive function f (x) one can

effectively calculate p(e) such that φp(e) (x) ≃ f (x).

3. But then g(x) = φp(x) (x) + 1 = ψU (p(x), x) + 1 is a total

computable function that is not primitive recursive.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 24/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Proof (1)

Sub(f ; g1 , g2 , · · · , gm ) denotes the function obtained by substituting

g1 , · · · , gm into f . (f is m-ary; gi are n-ary for some n).

Rec(f , g) denotes the function obtained from f and g by recursion (f is

n-ary, g is (n + 2)-ary for some n).

S denotes the function x + 1

Uin denotes the projection function Uin (x1 , · · · , xn ) = xi .

For each primitive recursive function, we have a Plan to indicate the

basic functions used and the exact sequence of operations performed.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 25/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Example: f (x) = x2

g1 = Sub(S; U33 ): g1 (x, y, z) = U33 (x, y, z) + 1 = z + 1

g2 (x, 0) = U11 (x) = x,


g2 = Rec(U11 ; g1 ):
g2 (x, y + 1) = g1 (x, y, g2 (x, y)) = g2 (x, y) + 1
So g2 (x, y) = x + y

g3 = Sub(g2 ; U13 , U33 ): g3 (x, y, z) = g2 (x, z) = x + z


g4 (x, 0) = 0,
g4 = Rec(0; g3 ):
g4 (x, y + 1) = g3 (x, y, g4 (x, y)) = x + g4 (x, y)
So g4 (x, y) = xy

f = Sub(g4 ; U11 , U11 ): f (x) = g4 (x, x) = x2

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 26/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Effective Numbering
Now restrict our attention to plans for unary primitive recursive
functions. We can number these plans in an effective way. Define:

θn = the unary primitive recursive function

defined by plan number n

Since every primitive recursive function is computable, there is a total

function p such that for each n, p(n) is the number of a program that
computes θn .

θn = φp(n) .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 27/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Computability of p(n)

We know how to obtain a program for the function Sub(f ; g1 , · · · , gm )

given programs for f , g1 , · · · , gm ;

We know how to obtain a program for the function Rec(f , g) given

programs for f , g;

We have explicit programs for the basic functions.

Hence, given a plan for a primitive recursive function f involving

intermediate functions g1 , · · · , gk , we can effectively find programs
for g1 , · · · , gk and finally f .

Thus, by Church’s Thesis, there is an effectively computable function

p such that θn = φp(n) .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 28/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Construction of Total Non-Primitive Recursive Function

For every primitive recursive function θn , we use a diagonal

construction as follows:

g(x) = θx (x) + 1
= φp(x) (x) + 1
= ψU (p(x), x) + 1

g is a total function that is not primitive recursive, but g is

computable, by the computability of ψU and p.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 29/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Outline

1 Universal Functions and Universal Programs

2 Application of the Universal Program

3 Effective Operations on Computable Functions

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 30/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Function Operation

Fact. There is a total computable function s(x, y) such that

φs(x,y) = φx φy for all x, y.

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 31/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Function Operation

Fact. There is a total computable function s(x, y) such that

φs(x,y) = φx φy for all x, y.

Proof. Let f (x, y, z) = φx (z)φy (z) = ψU (x, z)ψU (y, z).

By S-m-n Theorem there is a total function s(x, y) such that
φs(x,y) (z) ≃ f (x, y, z).

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 31/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Set Operation

Fact. There is a total computable function s(x, y) such that

Ws(x,y) = Wx ∪ Wy .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 32/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Set Operation

Fact. There is a total computable function s(x, y) such that

Ws(x,y) = Wx ∪ Wy .

Proof. Let

1, if z ∈ Wx or z ∈ Wy ,
f (x, y, z) =
undefined, otherwise.

By S-m-n Theorem there is a total function s(x, y) such that

φs(x,y) (z) ≃ f (x, y, z). Clearly Ws(x,y) = Wx ∪ Wy .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 32/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Inversion

Let g(x, y) be a computable function such that

(a) g(x, y) is defined iff y ∈ Ex ;
(b) If y ∈ Ex , then g(x, y) ∈ Wx and φx (g(x, y)) = y. (i.e.,
g(x, y) ∈ φ−1x ({y}))

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 33/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Inversion

Let g(x, y) be a computable function such that

(a) g(x, y) is defined iff y ∈ Ex ;
(b) If y ∈ Ex , then g(x, y) ∈ Wx and φx (g(x, y)) = y. (i.e.,
g(x, y) ∈ φ−1x ({y}))

By S-m-n Theorem, there is a total computable function k such that

g(x, y) ≃ φk(x) (y). Then from (a) and (b) we have:
(a’) Wk(x) = Ex ;
(b’) Ek(x) ⊆ Wx ; If y ∈ Ex , then φx (φk(x) (y)) = y.

Hence if φx is injective, then φk(x) = φ−1

x and Ek(x) = Wx .

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 33/34

 Universal Functions and Universal Programs
Application of the Universal Program
Effective Operations on Computable Functions

Application: Effectiveness of Recursion

Consider f defined by the following recursion

(n) (n)
f (e1 , e2 , x, 0) ≃ φe1 (x) ≃ ψU (e1 , x),

and
(n+2)
f (e1 , e2 , x, y + 1) ≃ φe2 (x, y, f (e1 , e2 , x, y))
(n+2)
≃ ψU (e2 , x, y, f (e1 , e2 , x, y)).

By S-m-n Theorem, there is a total computable function r(e1 , e2 ) such

that
(n+1)
φr(e1 ,e2 ) (x, y) ≃ f (e1 , e2 , x, y).

CSC363-Computability Theory@SJTU Xiaofeng Gao Universal Program 34/34