Key idea:
To identify a single program that can simulate any
program and all programs
by
computing the same functions computed by these other programs, one at a
time.
Program: P, taking n inputs, X1, X2, …,
Xn
yP(X1,X2, …,
Xn) : A PC function computed by this program P.
We define a function as
follows:
U (X1,X2, …,
Xn, #(P)) = yP(X1,X2, …,
Xn)
for all P’s
and #(P)’s
The question is:
Is this
function PC, that is, is there a program that takes
n+1
inputs one of
which is a program number that computes the same
function as
this input program number computes for any program and
for all
programs provided that these programs take exactly n
inputs???
The answer is “YES”: THM3.1 (page
70).
Since this program is unique among programs of n+1
inputs, we call it a
“Universal” program, Un, and the PC function
computed by this program a “Universal Function”
which we denote by:
f (X1,X2, …,
Xn, y) = yP(X1,X2, …,
Xn)
where y used
as another argument of this Universal function is #(P) representing
a
program with
n inputs.
STP(X1,X2, …, Xn, y,t)
<->
A program represented by y stops in t or fewer steps on inputs X1,X2, …,
Xn
(here, number
of steps means the same as number of times instructions of a program have
actually been executed by the computer)
<->
There is a
computation (of length of at most t+1) by a program y,
beginning
with inputs of X1,X2, …, Xn
In other
words, in this predicate we wonder if a certain arbitrary program
stops
in a finite number of steps or in a finite amount of
time.
Although the question of whether or not an arbitrary
program ever stops is unsolvable
this somewhat restricted question of whether or not a
program stops within a finite amount of time is solvable as this predicate is
shown to be PR, more than just “Computable”.
The “Step-Counter Theorem” of page 74 proves that it is
PR.
This THM shows some PR functions/predicates such
as:
Note:
1. The state
(that shows current values of all program variables at any point in
time)
is given by:
k
z =
P Pn vn where k is the number of all
program variables and vn is the current
n=1
value of n-th variable and
Pn is the n-th
prime.
2. The current snapshot is given by:
<i,
z> where i is the next
instruction sequence number to be executed
and z is the current State.
a. The label of an
instruction
LABEL(i,y) =
l(s(y+1,i)) where is a
program number and i is the sequence
number of an instruction.
b. The
variable of an instruction
VAR(i,y) = r(r(s(y+1,i))) +
1
c. The type of an instruction
INSTR(i,y) =
l(r(s(y+1,i)))
d. The destination label of an instruction
LABEL’(i,y) =
INSTR(i,y) – 2 (proper subtraction).
NOTE: In the above four functions, when i > Lt(y+1), that is, when the
program
termination condition has been reached, the value is 0 each except
VAR().
In particular, INSTR() is zero.
e. Four Predicates to indicate the effect of executing the next
instruction (as represented
by the current
snapshot).
SKIP(x,y)
= just go to the next instruction w/o changing any
variable
where x is the current snapshot and y is the program
number.
INCR(x,y)
= to increment a variable by one. (The instruction type is simply
one)
DECR(x,y)
= to decrement a variable by one. (The instruction type is two
and
the involved variable is at
least one)
BRANCH(x,y) = to actually make a conditional branch (as the instruction
is
IF-GOTO and the involved variable is non-zero)
NOTE: When x, the current snapshot, has the positive program termination
indicator,
None of above four predicate is true.
f. The successor snapshot of
the current snapshot, x (y is
program number)
SUCC(x,y)
= <l(x)+1, r(x)>
if SKIP(x,y)
= <l(x)+1, r(x). pVAR(l(x),y ) >
if INCR(x,y)
= <l(x)+1, int(r(x)/PVAR(l(x),y))> if
DECR(x,y)
=
<min
[LABEL(i,y)=LABEL’(l(x),y)], r(x)> if
BRANCH(x,y)
i<=Lt(y+1)
= <Lt(y+1)+1, r(x)>
otherwise (Program
termination)
NOTE: Once the current snapshot, x, has the positive program termination
indicator,
SUCC(x,y) = x, no change to the next successor
snapshot.
g. The
initial snapshot (before the program execution)
n
INIT(X1,X2, ..., Xn) =
<1, P (P2i Xi )>
n=1
h. Predicate to test if the
current snapshot, x, represents the
program termination
TERM(x,y)
= l(x) > Lt(y+1)
i. Function to give
the snapshot exactly after executing n instructions of
a
program, y.
SNAP(X1,X2, ..., Xn, y,0) = INIT(X1,X2, ...,
Xn)
SNAP(X1,X2, ..., Xn, y, t+1)
= SUCC(SNAP(X1,X2, ..., Xn,
y,t), y)
Finally, STP() can be represented as follows:
STP(X1,X2, ..., Xn, y, t) = TERM (SNAP(X1,X2, ..., Xn, y, t),
y)
THM3.3 (page75):
Key idea: Associating any given PC function with a PR
Predicate
Given a PC function, f(X1,X2, ..., Xn), we can find a PR
predicate
such that
f(X1,X2, ..., Xn) =
l( min R(X1,X2, ..., Xn, z))
z (unbounded
minimalization)
If we let z = <y,t>, then
(where y is the function value and t is the number of
program
execution steps at any point in time before
termination)
R(X1,X2, ..., Xn, <y,t>) can be:
STP (X1,X2,
..., Xn, y0, r(z)) and
l(z) =s( r(SNAP(X1,X2, ..., Xn, y0, r(z))),1)
where y0 is the program for this PC function.
Characterization of the class of all PC functions.
THM3.4 (page76)
A function is PC if and only if it can be obtained from the INITIAL
functions
by a finite number of applications of:
composition
primitive recursion and
minimalization (Unbounded)
Definition of Proper Minimalization:
f(X1,X2, ..., Xn) = min P(X1,X2, ..., Xn, t)
t
If the above function is total, we say that we are applying a
‘Proper’
Minimalization.
Characterization of the class of all computable
functions.
THM3.5 (page-77)
A function is computable if and only if it can be obtained from INITIAL
functions by
a finite
number of applications of:
composition, primitive recursion and proper
minimalization.