Program
Encoding
Key idea: To
represent any arbitrary program by a unique integer
1.
Encoding each instruction
2.
Program = A sequence of integers where each integer represents an
instruction
3.
Program = The Godel
number of this sequence – 1.
Instruction encoding:
Many ways
The SIMPLE language with only three
instructions will help simplify
this
process.
1. Order variables: Y, X1,Z1,X2,Z2,X3,Z3, ...
2. Order statement labels: A1,B1,C1,D1,E1, A2,B2,C2,D2,E2, ...
3. #(instruction) = <a, <b,c>>
a: represents the label number if a label is
included.
0 means no label
1 means that
the included label is A1 or A
2 means that it is A2, and so on.
b: represents the type of the
instruction
0 means V <- V
(For the sake of completeness)
1 means V <-
V+1
2 means V <-
V-1
3 or higher
means “IF V <> 0 GOTO L” and also the value (b)
specify the destination label.
So, 3 means the
destination label is A or A1
4 means it is B1, 5 means it is C1, and so forth
c: represents the variable of the
instruction
0 means Y, 1
means X1, 2 means Z1, 3 means X2, 4 means Z2, and so
forth.
EX:
X1 <- X1 + 1
<0, <1,1>>
[B2] IF X2
<> 0 GOTO C2 <7,
<10,3>>
Y <- Y
<0, <0,0>> = 0
Program
number
#(P) = [#(I1),
#(I2), #(I3), ..., #(Ik)] – 1 where k is the length of
a program.
So, it can be 0 and that represents an
empty program.
Halting
Problem
Unsolvable problem: Not a PC
function (predicate)
Formally,
let
Halt (x,y) be a predicate that
indicates “Whether or not a program y eventually
halts on input x”
As such, it is a predicate
and hence it is total, that is, it has a value for all x and for
all
y.
However, it is not
computable and not PC.
THM2.1 (Page
68)
Halt (x,y) is not computable (actually
not partially computable)
Proof: (Proof by
contradiction)
Consider the following program P:
[A]
IF Halt(X,X) GOTO A
So, clearly, for any X and all X’s,
1. if Halt(X,X) is true P does not halt on X
and
2. if Halt(X,X) is false P does halt on
X.
So, P halts on X if and only if Halt(X,X) is
false.
P halts on X
<->
Halt (X, #(P))
<-> not (Halt
(X,X))
Since above holds for
any X, we let X = #(P) = the number of this
program.
The result is:
Halt(#(P), #(P))
<-> not
(Halt(#(P),#(P))): A Contradiction.
QED.
In a way, the predicate fails to answer the question of program halting
at least
for this particular program if it answers for
other programs at all.
Church’s Thesis (Hypothesis)
There exists an algorithm for solving a function (problem) if and only
if
there is a program in this SIMPLE language that
computes the function.
In essence, it is to say that Solvability of a function is equivalent to
the
existence of a program that computes
it.