Computability

   The issue of exactly what computers can compute and what they cannot.

   Tool:

      1.   Turing machines: Traditional

              Quadruples (One version)

                        Qi        Sj         Sk        Ql

                        Qi        Sj         R         Ql

                        Qi        Sj         L          Ql

              Very tedious and difficult to analyze

      2.   A SIMPLE Language:

               Less tedious and not so difficult to analyze.

 

A SIMPLE Language

 

   1.      Numeric processing: Only non-negative integers

 

   2.      Variables:

               X1, X2, X3, ...          Input variables that assume intended input values each.

               Y                              Only one output variable initialized to zero

               Z1, Z2, Z3, ...                       Local variables initialized to zero each

 

   3.      Three basic statements:

               V  =  V+1     // same variable

               V  =  V-1      // same variable,  0-1 is 0

               IF V <> 0  GOTO L            // L is the Lable of the destination statement

 

   4.      Some Macros : to make the language more powerful without changing the very

            definition of the language.

           

            GOTO L

            V = 0

            V1 = V2

            V1 = V2 + V3

            V1 = V2 – V3

            V1 = V1 * V3

 

   5.      Example Macro Expansions

 

            GOTO L

                        Zi = Zi +1

                        IF Zi <> 0 GOTO L

 

            V = 0

                        [A]       V = V-1

                                    IF V <> 0  GOTO A

 

            V1 = V2 (V2 should not be changed in the process)

                                    V1 = 0

                        [A]       IF V2 <> 0  GOTO B

                                    GOTO C

                        [B]       V2 = V2 - 1

                                    V1 = V1 + 1

                                    V3 = V3 + 1    // A new local variable

                                    GOTO A

                        [C]       IF V3 <> 0 GOTO D

                                    GOTO E         // Done

                        [D]       V3 = V3 – 1

                                    V2 = V2 + 1

                                    GOTO C

 

            V1 = V2 + V3 (V2 and V3 must remain the same and V1 and V3 are distinct)

                                    V1 = V2

                                    V4 = V3          // V4 is a new local variable

                        [B]       IF V4 <> 0 GOTO  A

                                    GOTO  E        // done

                        [A]       V1 = V1 + 1

                                    V4 = V4 – 1

                                    GOTO B

 

Program execution

            1.         State

                        A list of equations of form V=m where V is a variable and m its current

                        for all variables of a program.

                        Exactly one equation for each variable.

                        So, a state of a program represents a current computational result.

            2.         Snapshot (Instantaneous Description)

                        s = (i, state)     where i is the next instruction to be executed and

                                                initially it is 1 when a program is about to start.

                        When i is n+1 (where n is the number of instructions of a program)

                        the program stops.

            3.         Terminal snapshot

                        When the first component of a snapshot is n+1 indicating that the

                        Program is about to stop.

            4.         Successor snapshot (j, state2) of a non-terminal snapshot (i,state1)

                        a.         case-1: i-th instruction is V = V+1

                                    j = i+1

                                    The equation V=m of state1 will be replaced by the equation

                                    V = m+1 and the result becomes state2.

                        b.         case-2: i-th instruction is V = V-1

                                    j = i+1

                                    The equation V=m of state1 will be replaced by the equation

                                    V = m-1 if m>0 or V=0 if m=0 and the reuslt becomes state2.

                        c.         case-3: i-th instruction is IF V<>0 GOTO L

                                    Two subcases (in both cases, state2 becomes the same as state1)

                                    3a: when V=0 is an equation of state1.

                                          j=i+1 and state2 is the same as state1

                                    3b: when the equation V=m of state1 has m>0

                                        i.  when at least one instruction of the program has the label L

                                             j will become the least number of an instruction with label

                                             L 

                                        ii. when no instruction of the program has the label L

                                             j = n+1   (Terminal snapshot for the program to terminate)

 

Partially Computable Functions

   We associate each program P with m inputs, X1, X2, ..., and Xm with a function of

   as many arguments (m) as follows:

            1. Y = y_P  (X1, X2, ..., Xm) is a partially computable function

            2. The value of this function is the same as the value of the output variable Y

                of this program P whenever the program terminates, i.e., whenever there is

    a computation to this program.

            3. When there is no computation, i.e., there is no terminal snapshot, or

    when the program does not terminate, the value of this function is    

    undefined.

 

Computable functions:

            Partially computable functions that are total (defined for all possible

            Arguments values).

So, by definition, a program computing a Computable function must terminate in all cases, i.e., for all possible inputs.

 

Example:         P1

                        Y = X1

            [A]       IF X2 = 0  GOTO E

                        Y = Y+1

                        Y = Y+1

                        X2 = X2-1

                        GOTO  A

 

                        y_P1 (X1,X2) = X1 + 2*X2 which is total and hence computable.

 

Example:         P2

                        Y = X1

            [A]       IF X2 = 0  GOTO E

                        X2 = X2 – 1

            [B]       IF X2 = 0  GOTO  B

                        Y = Y+1

                        Y = Y+1

                        Y = Y+1

                        Y = Y+1

                        X2 = X2 - 1

                        GOTO  A       

 

                   y_P2 (X1,X2) = X1 + 2*X2 if X2 is even  and undefined otherwise.

                        So, this function is partially computable but not computable.

                        Note that the program does not terminate if X2 is odd thereby making the

function undefined in such cases.

 

 

 

All Programs = All Partially Computable Functions.

In order to check to see if a function is PC (Partially Computable), we have to find or write a program that computes this function. And, finding or writing a program in this SIMPLE language is certainly tedious and involved.

 

So, we would like to use some tools for confirming that a function is PC without having to a write a program.

 

Two tools:       Operations:

Composition and Primitive Recursion (or just Recursion)

 

Composition

 

1. Simple case:            h(X) = f(g(X))

In this case, if two functions, g(X) and f(X), are PC, then the resulting new function h(X) is also PC.

            Or if they are both computable, so is the resulting new function h(X).

 

            EX:      g(X) = X+1

                        f(X) = 2*X

                        h(X) = 2*(X+1) = 2*X + 2

                        As g(X) and f(X) are computable, h(X) is also computable.

 

2. General case:

            We have following computable functions:

                        f(X1, X2, ..., Xk)

                        g1(X1, X2, ..., Xn)

                        g2(X1, X2, ..., Xn)

                                    .

                                    .

                                    .

                        gk(X1, X2, ..., Xn)

            That is, one f-function of k arguments and

            k g-functions of n arguments each.

 

            In this case, we can get the following new function that is also

            computable:

                        h(X1, X2, ..., Xn) =

                        f(g1(X1,X2, ..., Xn), g2(X1,X2, ..., Xn) , ..., gk(X1,X2, ..., Xn))

 

            Note that this proof says that if f-function and all g-functions are PC

            then h-function is also PC.

 

Recursion

 

1. Simple case.

            We have two Computable functions:

                        f() of zero argument, namely a constant

                        g(X1,X2).

            In this case, we can build a new Computable function as follows:

                        h(0) = f()

                        h(X+1) = g(X,h(X))

           

EX:

                        f() = 1

                        g(X1, X2) = (X1+1)*X2 = X1*X2 + X2

                        In this case, the new h-function will look like:

                          h(0) = 1

                          h(1) = g(0, 1) = 1

                          h(2) = g(1, 1) = 2

                          h(3) = g(2, 2) = 6

                          h(4) = g(3, 6) = 24

                          h(X) = 1*2*3*... * X = factorial

 

2. General case.

            We have two computable functions:

                        f(X1, X2, ..., Xn) with n arguments, n>=1

                        g(X1, X2, ..., X _n+2 ) with n+2 arguments

            In this case, we obtain a new computable function of n+1 arguments

            by Primitive Recursion as follows:

                        h(X1, X2, ..., Xn, 0)    =  f(X1, X2, ..., Xn)

                        h(X1, X2, ..., Xn, 1+t) =  g(X1, X2, ..., Xn, t, h(X1,X2, ..., Xn,t))

            Note that the new h-function is defined in terms of itself, and hence the

            operation name, Recursion.  

 

            THM-2.2 (page 41) says that if the f-function and the g-function are

            Computable then so is the resulting h-function.

            Also, if they are PC, the new resulting function is PC.

 

A Class of functions that are bound to be Computable without writing a program.

 

This class is called a class of Primitive Recursive functions (PR).

   Definition:  Primitive Recursive Functions

1.      Basis:       

Following three initial functions are PR.

                        a.         S(X) = X+1                              // Successor function

                        b.         N(X) = 0                                  // Zero function

                        c.         P_k (X1, X2, …, Xn) = X_k        // Projection function   

2.      Applications of two operations

Any function that can be obtained from three initial functions by applying any sequence of two operations above (Composition and Recursion) is PR.

3.      Closure.

No other function is PR.

  

   Every PR function is Computable.

   Note that the Converse is not true, that is, there is a computable function 

   that is not PR.

   Note that a predicate is a total function that assumes only True(1) or

   False(0).

   So, a predicate is just a special case of total functions and a special case of

   functions.

 

Some more powerful operations that preserve function closure properties.

    Just like above two operations that preserve function closure properties

     (whether functions are PR or Computable or PC), we would like to find

     other more powerful operations that preserve the same.

 

1.      Definition by Cases.

Given        two functions f (X1,X2, …, Xn) and g (X1,X2, …, Xn)

       and       a predicate  P (X1,X2, …, Xn),

we define a new function  h (X1,X2, …, Xn) as follows:

 

h (X1,X2, …, Xn) = f (X1,X2, …, Xn) if P(X1,X2, …, Xn)

                              = g (X1,X2, …, Xn) otherwise.

 

Also, note that in general we can have any number of predicates provided that no two predicates hold true for the same set of arguments, that is, at most one predicate does hold for any set of argument values.

EX:

      P1(X1,X2,X3,X4) = X1+X2>X3+X4 and X1<X3

      P2(X1,X2,X3,X4) = X1 > X3

      P3(X1,X2,X3,X4) = X1=X3 and  X2 < X4

      In this example, we see that at most one of them is true for any

      value of X1 and X2 and X3 and X4.

      Furthermore, when X1=X3 and X2=X4, none of them is true.

 

2.      Iterated Operations

Given a function f (t,X1,X2, …, Xn), we define a new function as

follows:                         y

g (y,X1,X2, …, Xn) =  S  f (t,X1,X2, …, Xn)

                                     t=0

 

                                      y

h (y,X1,X2, …, Xn) =  P  f (t,X1,X2, …, Xn)

                                     t=0

                  Note that the summation (or product) can begin at any given fixed

                  value instead of 0.

 

3.      Bounded Quantifications

Defining a new predicate from a predicate.

 

Given a predicate, P(t,X1,X2,X3, …, Xn), we define another predicate

as follows:

      U (y,X1,X2,X3, …, Xn) = ($t) P(t,X1,X2,X3, …, Xn)

                                                  t <= y (where ‘$’ is the Universal quantifier.

 

      E (y,X1,X2,X3, …, Xn) = (%t) P(t,X1,X2,X3, …, Xn)

                                                   t <= y (where ‘%’ is the Existential

                                                               quantifier.)

Note that these two new predicates are expressed in terms of iterated operations.                                 

                                                      y

   ($t)  P(t,X1,X2,X3, …, Xn) =  P  P(t,X1,X2, …, Xn) 

   t <= y                                        t=0

 

Also note that it is the boundedness of the operations that make the operations closure-property-preserving. That is, the same operations when not bounded are not to be closure-property-preserving, in general.

           

            4.   Bounded Minimalization    

                  Defining a new function from a predicate.

                  Given a predicate,  P(t,X1,X2, …, Xn) , we define a function as

                  follows:

                        g(y,X1,X2, …, Xn) =  min P(t,X1,X2, …, Xn) 

                                                              t <= y

                          which is the least value of t (<=y) such that the predicate is

                          satisfied (true) when it is satisfied for at least one value of

                          t <= y or else zero.

 

                  Now, this function can be written as:

                                                               y      u

                        g(y,X1,X2, …, Xn) =   S      P    a(P(t,X1,X2, …, Xn))

                                                               u=0  t=0

                         except that the maximum possible value of y+1 is treated as 0

                         instead.

 

                  EX:  Suppose that P(t,X1,X2) is true when t=4 but not for any

                          smaller value of t.  That is,

                                    P(0,X1,X2) = 0

                                    P(1,X1,X2) = 0

                                    P(2,X1,X2) = 0

                                    P(3,X1,X2) = 0

                                    P(4,X1,X2) = 1 and so on.

 

                                    So, g(y,X1,X2) = min P(t,X1,X2) is 4 when y is at least 4  

                                                                    t <= y

 

                                    In this case, the above formula yields, if y is at least 4,:

                                    a(0) +  a(0)*a(0) + a(0)*a(0)*a(0) +

a(0)*a(0)*a(0)*a(0) +

a(0)*a(0)*a(0)*a(0)*a(1) +

a(0)*a(0)*a(0)*a(0)*a(1)*a(?) +

a(0)*a(0)*a(0)*a(0)*a(1)*a(?)*a(?) +  ... +

 

            EX: Bounded Minimalization:

Let d(x,y) = the integer quotient of x/y. So d(10,4) is 2 and d(100,30) is 3.

            We can express this function as:

                        d(x,y) = min ((t+1)*y > x) = P(t,x,y)

                                    t <= x

 

            (Unbounded) Minimalization

 

                        g(X1,X2, …, Xn) =  min P(t,X1,X2, …, Xn)

                                                            t

            The value of above function is the least value of t for which the

            predicate P is true if there is one.     

If there is no value of t for which the predicate P

            is true, then it is not defined. Thus unbounded minimalization

can easily produce a function that is NOT total.

For example, the following function is not defined when x<y and hence

it is not total:

            x-y = min (y+t=x)

                        t 

            However, if the predicate is computable, the unbounded

minimalization produces a PC function.

 

Pairing Function

 

            Idea: To define a unique number for a pair of two numbers so that

            1. we can use one number instead of the two numbers we have.

            2. from the one number we use, we can always get back the

original two numbers we had.

 

            Definition:       <x,y> = 2^x (2*y+1) - 1

 

2^x (2*y+1) > 0 and so 

2^x (2*y+1) = <x,y>+1

           

            EX:      <0,0>   =          1*1-1   =          0

                        <1,0>   =          2*1-1   =          1

                        <0,1>   =          1*3-1   =          2

                        <2,0>   =          4*1-1   =          3

                        <0,2>   =          1*5-1   =          4

                        <1,1>   =          2*3-1   =          5

 

            Note that if z=<x,y>, we can figure out x and y uniquely, that is,

            if <a,b> = <c,d> then a=c and b=d.

 

            EX:      <x,y> = 95

                        2^x (2*y+1) = 95+1 = 96

Since (2*y+1) is at least one and odd, X cannot be  0 nor 1 nor 2 nor 3 nor 4 (16)  but 5 as 2^x = 32 and (2*y+1) = 3

                        So x=5 and y=1 and this is the only possible solution.

 

            Given any number z, we can figure out two numbers x and y uniquely

such that z = <x,y>.

            In fact, we can define two PR functions:

                        r(z) and l(z) such that z=<l(z), r(z)>

 

            Definitions of l(z) and r(z)

            Note that <x,y> is at least as large as x or y.

 

                        l(z) = min   [(%y) z=<x,y>]

                                  x<=z   <=z        

 

                        r(z) = min   [(%x) z=<x,y>]

                                  y<=z   <=z

 

            THM8.1 (Pairing Function Theorem)

            The functions <x,y>, l(z), and r(z) have the following properties:

            1. they are PR

            2. l(<x,y>) = x

            3. r(<x,y>) = y

            4. z= <l(z), r(z)>

            5. l(z), r(z) <= z

 

          Godel number of a sequence of numbers

            Idea: Representing a sequence of numbers by a unique (one) number        

 

            Given a sequence of numbers, (a1,a2, .., an)

                                        n

            [a1,a2, ..., an] =  P  p_i ^ai    

                                        i=1

 

            EX: 

              [5,6,2] = 2⁵ 3⁶ 5² = 2*2*2*2*2* 3*3*3*3*3*3* 5*5

 

            Uniqueness Property: THM8.2 (Page 61)

            If [a1,a2,a3, .., an] = [b1,b2,b3, .., bn] then

            ai = bi for all i, namely, for i=1, ..., n    

 

            Note that, however, [a1,a2,a3] = [a1,a2,a3,0] = [a1,a2,a3,0,0]

            That is, the uniqueness does not include trailing zeroes in the sequence.

 

            A PR function to get back each number of a sequence

            (Sequence Number Function)

 

            Suppose that  x = [a1,a2, ..., an]

            s(x,i) = (x)_i  =  a _i  for  1 <= i <= n

                               =  0  for i=0 or  i>n.

            EX:

              s([5,0,3],1)     =  5   

              s([5,0,3],2)     =  0

              s([5,0,3],3)     =  3

              s([5,0,3],0)     =  0

              s([5,0,3],i)      =  0  for i = 4,5,6,7,8, ...

 

            We can define this function as follows:

 

                        s(x,i) =  min (not Div (p ^t+1 _i   , x))

                                      t<=x

                        where Div (x,y) is true iff x is a divisor of y.

            So,

                        Div (2*2, [3,2,4])   =

                        Div (2*2*2, [3,2,4])  =

                        Div (3*3, [3,2,4])  =

                        Div (5*5*5*5, [3,2,4])  =  true

            But,     Div (2*2*2*2, [3,2,4])  =

                        Div (3*3*3, [3,2,4] = 

Div (7, [3,2,4])       =   false

            Note     Div (0,x) = false where 0 = p₀

                        So, s(x,0) = 0 for all x.

                        Also, Div(x,0) = true for all x except 0

                        So, s(0,i) = 0 for all i

 

            A PR function for determining the length of a sequence

               Lt(X)  where X is the Godel number of a sequence.

 

               Lt ([3,6,2])  =  3

               Lt ([3,6,2,0]) = 3

               Lt ([3,6,2,0,0])  = 3

 

               Lt(x)  =  min   [ s(x,i) <> 0 & ($t) (t>i -> s(x,t) = 0)]

                              i <= x                         t <= x

 

            Note Lt(0) = Lt(1) = 0

            The first one is for a non-existing sequence and the second one is

            for a sequence of length 0.

For this function to be PR, it must be defined for all values of its argument including 0 and 1.

 

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.

 

    Theorem: Unsolvability of the Halting Problem

 

    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.

 

 

Universal Program

 

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

   y_P(X1,X2, …, Xn) : A PC function computed by this program P.

 

We define a function as follows:

U (X1,X2, …, Xn, #(P))   =    y_P(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”

 

Since this program is unique among programs of n+1 inputs, we call it a

“Universal” program, U_n, and the PC function computed by this program a “Universal Function”

which we denote by:

f (X1,X2, …, Xn, y) =  y_P(X1,X2, …, Xn)

where y used as another argument of this Universal function is

#(P) representing a program with n inputs.

 

Step-Counter predicate

 

          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 “Computable”.

 

Notes:

1. The state (that shows current values of all program variables at any 

     point in time) is given by:

                           k

     z =         P    P_n ^vn   where k is the number of all program     

                  variables and vn is the current value of n-th   

                          n=1      variable and  P_n  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). p_{VAR(l(x),y )} >          if INCR(x,y)

                           = <l(x)+1, int(r(x)/P_VAR(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   (P_2i ^Xi )>

                                                            i=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)

 

Normal Form Theorem  

         

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.   

         

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.

         

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.

 

 

 

          Recursively Enumerable (RE) Sets of numbers

 

          Key idea: Sets that are equivalent to all PC functions of

          one argument.

 

          Definitions:

          Let g(X) be a PC function of one argument.   

          Let S = {n | g(n) is defined}

          This set is RE.

 

          Let P(X) be a computable predicate.

          Let  S = {n | P(n) is true}

          Then, this set is Recursive

 

          Observe following characteristics of RE sets:

 

          1. A set is Recursive if and only if both it and its complement are RE.

          2. If two sets R and S are RE then the following is each RE:

                   their Union

                   their Intersection

          3. An RE set may not be Recursive. However, every Recursive set is RE.

          4. The Membership question: Predicate Member(R,x)

Given a set R and a possible member x, the question of whether or

not x is indeed a  member of the set

             Member(R,x) is computable if R is Recursive but not if R is RE

   (not always)

 

          Enumeration of all RE sets

 

          Let W_n  = { x |  f (x,n) is defined}

 

Note that above set W_n  is RE and it DOES correspond to a PC function of one argument computed by a program whose number is n.

Also that when a program has more than one input variable, we can assume that the program computes a PC function of just one argument by assuming that only one input variable actually takes on an input value and all other input variables

          are zero initially.

 

All non-negative integers represent

a.  all programs with any number of input variables.

b.  all PC functions of any number of arguments.

c.  all PC functions of exactly one argument.

d.  all RE sets of numbers:

 

 

Enumeration:

 

W₀ ,   W₁ ,   W₂ ,     W₃ , …,     W_infinity                                                     

 

As above enumeration certainly contains all RE sets of numbers, for any given RE set R, it is the case that there is at least one k such that

          R = W_k

 

Now we would like to identify a set that is RE but not Recursive.

 

Consider a set:     K = {x | x is in  W_x }

That is, if j is in this set K, it is also in its corresponding RE set, W_j

as we can have any number j corresponding to the set W_j

 

Now, we claim that the complement of this set K is not RE, and hence K is not Recursive while it is RE.

 

There is a Theorem that says:

The set K is RE but not Recursive.

 

Proof: (By contradiction)

 

Assume that ~K is RE.

So, there must an integer j such that  ~K =  W_j

Look us look at this integer j (as it is suspicious)

There are two possibilities regarding its belonging:

Case-1: j is in W_j

          Case-2: j is not  in W_j

Case-1:  j is in  W_j  so it must be in K by the definition of the set K

           But we are assuming that it is not in K by the definition of  W_j 

           A contradiction.

Case-2: j is not in  W_j  , so it must not be in K from the def of the set K.

          But we are assuming that it is in K from the def of   W_j              

          Again, a contradiction.

QED.

                                                                                   

Equivalence among Ranges of functions:

           

            Let R be a non-empty RE sets.

            The following are all the same:

                        The set R

                        The range of a certain PR function.

                        The range of a certain Computable function.

                        The range of a certain PC function.

 

           

            THM 4.8

            For any RE set B, we have the following equality:

            B =  {x |  (%t) R(x,t)) for a PR predicate.

            (Because R(x,t) can be STP(x,y,t) where y is the program corresponding to

             this RE set B and this STP() is PR)

 

            THM4.9

            For any non-empty RE set B, we have the following equality:

            B = {f(n) for n=0,1,2,3, ..., infinity} for a certain PR function.

            (That is, B is the range of this PR function)

            Key for the Proof: Using above PR predicate R(x,t) and picking an arbitrary

            element, say k, of this RE set B (since this set B is nonempty).

            We define the needed PR function f(x) as follows:

f(x) =   l(x) if R(l(x),r(x))

            k otherwise 

                        a. This function is PR. (We used Definition-by-Cases Operation)

                        b. Every f(x) is in this set B, from the very def of this function above.

                        c. Every element of B is the same as f(x) for some x.

                                    Let k be in B.

                                    Then R(k,t) is true for some t, and hence k is f(<k,t>)

                                        If R(k,t) is true R(l<k,t>, r<k,t>) is true and

                                        f(<k,t>) is the same as l(<k,t>) which k

 

            THM4.10

            For any PC function, f(x), we have a certain RE set B

            such that B = {f(x) | f(x) is defined}, that is, the set B is the same as

            the range of this PC function.

            Key idea for proof:

            Find a corresponding PC function to this RE set we need.

            Define a function g(x) = 1 if x is in B, namely if x is f(u) for some u

                                                =  undefined otherwise, that is, if x is not in B.

Now, if this function g() is PC, then the set B is RE by the definition of

RE sets.

All we have to do is to show that g() is PC, namely, find a program.

            Key idea for constructing this Program:

            Given an input X, this program must check whether a program q

            computing the PC function f(u) stops (by possibly indefinitely

            incrementing the step counter of the STP()) for any u and when

            the program q stops it checks to see if the input X is the same as f(u).

            This program stops only when

            1. the program q stops for a certain input u of its own and

            2. the input X is the same as f(u) computed by q.

            So, this program must increment two values, x and t, in repeatedly checking

            STP(x,q,t) for checking the program q stops.       

 

Note that as long as the ranges of functions are concerned, PC functions are

            no different from PR functions or from Computable functions, as a group.

 

 

THM: Parameter Theorem

Key idea:  Finding a systematic way of eliminating any number of arguments of a

     function while preserving the identity of the function.

               The resulting new function with fewer arguments is a very special

               case of the original function.

 

For any n and m>=1, we have

f (X1,X2, ..., Xm, U1, U2, ..., Un, y)  =   f (X1,X2, ..., Xm,

S_n^m (U1,U2, ..., Un, y))  

where  S_n^m (U1,U2, ..., Un, y)  is PR.

 

Note that while the LHS of above equality shows a Universal function for functions

of m+n arguments the RHS shows one of m arguments.

 

An Example of non-RE set

         

            Let TOT =  {y | ($x) f (x,y) is defined}

So, this is the set of all programs that compute a total function (hence a Computable), each.

 

            THM6.1

            The set TOT is not RE.

 

            Proof: By contradiction.                                                        

1.  Assuming that it were RE.

            2.  There is a computable function g(x) since TOT is not empty such that

                 TOT = {g(0), g(1), g(2), g(3), ..., } and every program computing a computable

                              function of one argument is g(k), for some k, and is in this set.

            Trick: Define a Computable function whose program cannot be in this set (and list).

3.      Let h(x) =  f (x, g(x)) + 1 which is a function of one argument and by

definition it is computable.

            4.  Let p be the number of a program that computes this function h(x).

            5. We claim that there is no k such that g(k) = p

                So, this function h(x) is not computable, which is a contradiction.

            6.  Now, how we claim that there is no k such that p = g(k)

                 Suppose that there were a number k such that p=g(k) that is, the program p

                 computes a total function.

                 Let look at the fate of this mysterious number k.

                      a.   h(k) = f (k, g(k)) + 1 from def of h(x)

b.      h(k) = f (k, p) =  f (k, g(k)) from the def of universal functions.