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.