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

 

            Proof is in THM-1.1 on page 39.

            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 (refined) 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.

   Corollary 3.4 (on page 43)

            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.

 

Note that this THM uses a PR function denoted as a(X).

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   y<=z      

 

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

                                  y<=z  x<=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:

            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.