Reducibility

Key idea: For comparing RE sets.

 

Def:

          Let A and B be sets (of any kind)

          A is many-one reducible to B, written  A  <_m  B , if there is a computable

          function f(X) such that x is in A if and only if f(x) is in B.

 

Note that above definition covers all members of the set A but not necessarily those of the set B.

 

EX:   A = {0,1,2,3,4, ..., Infinity}

          B = {0,2,4,6,8, ..., 2*Infinity}

          f(x) = 2*x

               

          In the above case, clearly it is the case that A is many-one reducible to B

          as f(x) is computable and x is in A if and only if 2*x is in B

          In this example, both sets are covered entirely.

 

EX:   A = {0,2,4,6,8, ..., Infinity}

          B = {4,6,8,10,12,14, ..., Infinity}

          f(x) = x+10

 

          In the above case, set A is many-one reducible to set B. But, the set B is not

          covered entirely as 4,6, and 8 are not covered in the mapping.

 

In general, when a set A is many-one reducible  to set B, it is the case that the membership question for the set A is no harder than that for the set B.

 

THM6.2 (Reducibility)

 

Suppose that A is many-one reducible to B.

1. If B is recursive, then so is A.

2. If B is RE, then so is A.

 

Proof:

(1)

Since A is many-one reducible to B, from the definition, there is a computable

function f(x) such that A = { x | f(x) is in B }.

As B is recursive, B = { x | P(x) is true } for a certain computable predicate P(x).

Hence, A = { x | P(f(x)) is true } and the predicate P(f(x)) is computable making

the set A Computable (Recursive).

(2)

As B is RE, B = { x | g(x) is defined } for a certain PC function g(x).

Hence, A = { x | g(f(x)) is defined } and g(f(x)) is a PC function as it is the

composition of a PC function and a computable function.

 

Utility of this THM:

If we know that A is many-one reducible to B and it is not Recursive, then

we can conclude that B is not Recursive either.

Likewise if A is not RE, then we can conclude that neither is B.

 

EX:

          Let  K₀    = { <x,y> | f (x,y) is defined }

                        =  { u  |  f  (l(u), r(u)) is defined }

=  { u  |  g(u) is defined } where g(u) is  f (l(u),r(u))

                        which is PC.

          So,  K₀  is clearly RE.

          We can show that it is not Recursive by reducing K to K₀   

          We see that u is in K if and only if <u,u> is K₀   and  f(u) = <u,u> is

          Computable and so K is reducible to K₀

 

Actually, we can show every RE set is many-one reducible to K₀

Suppose that S is RE and let S = {x | g(x) is defined} where g(x) is PC.

So,  S = { x |  f (x,q) is defined } where q is the program number computing

the PC function g(x) .

So,  x is in S if and only if <x,q> is K₀  and <x,q> is a computable function of x.

This establishes the reducibility.

In a way, this set  K₀   is the most complicated RE set. So, call it m-Complete.

 

Definition: An m-Complete set

An RE set is m-Complete if any RE set is many-one reducible to it, like the set K₀

 

Once we find an m-Complete set S, we can use it in finding another m-Complete set

R by reducing S to R. In this case, we are establishing that R is also m-Complete

because the reducibility is a transitive relation.

 

In fact,  K₀   is reducible to K and so K is also m-Complete.

 

Proof of above Reducibility (Reduction)

 

1.  We need to identify a computable unary function f(x) such that

     x is in K₀  if and only if f(x) is in K, that is,

     <u,v> is  K₀    if and only if  f(<u,v>) is in K, that is,

     f (u,v) is defined if and only if   f ( f(<u,v>), f(<u,v>) ) is defined.     

2.  We want a program P with two inputs such that

      f (u,v) =  y_P (X1, <u,v>)  =   f (X1, S(<u,v>, #P))

      This equation becomes, for X1 = S(<u,v>, #P)

      f (u,v)  =  f ( S(<u,v>,#P), S(<u,v>, #P))

      As #P is a constant, S(<u,v>,#P) is a computable function of one argument

      as it is S(<l(x),r(x)>, #P).

 

3.  This program P computes  f (u,v) which is  f (l(X2),r(X2))

     So, P may have just one instruction :

          Y =  f (l(X2),r(X2))                                  

        

THM7.1 (Rice’s Theorem)

A sufficient condition for Non-Recursive Sets

Suppose that t  is an infinite set of PC functions of one argument without all PC functions. Then it is not Recursive.

Note that there is at least one function in this set t  and at least one function not

in this set by definition. We call the first f(x) and the second g(x).

Also note that a set of PC functions is the same as a set of numbers of programs that

computes these PC functions.

 

Proof:  By reducibility of the set K to this set t.

 

1.   Let h(x) be the empty function that is undefined for all x’s, namely its domain

      is empty.

2.   We assume that h(x) is not in set  t.

      a.          Consider the following program p:

                   Z <-  f (X2,X2)

                   Y <-  f(X1)

                    So,  f (X1,X2,#p) = f(X1) if  f(X2,X2) is defined and

                                                      undefined otherwise.

       b.         Now, consider the following program we get from above program p:

                   X2 <- k                 // where k is a constant

                   Z <-  f (X2,X2)

                   Y <-  f(X1)

          By definition, above program is S₁¹ (k,#p) which is a Computable function

          of k as #p is fixed.

        c.         Now we can check the relationship between the set K and this set t.

          1.       Suppose that k is in K   <->

                   f (k,k) is defined  <->

                   f (X,  S₁¹ (k,#p))  =  f(X) for all X’s <->

                   S(k,#p) which can be taken as a computable function of k is in t

                   as f(X) is.

          2.       Suppose that k is not K, then S(k,#p) must not be in  t.           

                   k is not in K                   <->

f(k,k) is not defined.      <->

f(X, S(k,#p)) is undefined for all X’s         <->

f(X,S(k,#p)) = h(X)       <->

S(k,#p) is not in t.

          This establishes the wanted reducibility as h(X) is not in t.

          So, in this case K is reduced to this set t. 

3.   Suppose that h(X) is in this set  t. 

      We get analogous result when we consider the following program p:

                   Z <-   f(X2,X2)

                   Y <-   g(X1)

      And, in this case,  S(k,#p) will represent the following program:

                   X2 <- k

                   Z <-   f(X2,X2)

                   Y <-   g(X1)

       In this case, we will conclude that:

                   k is in K  <-> S(k,#p) is in ~t

                          (as h(X) is in t  now and g(X) is in ~t)

       So, we are reducing K to ~t in concluding that  ~t  is not Recursive.

       This means that t is not Recursive.

4.    Hence, this set t is not Recursive.                           QED.

       This means that its membership question is unsolvable.     

 

Significance of Rice’s THM:

 

Any infinite set of PC functions (or of programs) with at least one possible member

missing is not Recursive and hence the membership question of any such set is unsolvable.

Examples of such sets:

          a. Set of all PR functions of one argument.

          b. Set of all Computable functions of one argument.

          c. Set of all PC functions of one argument but without at least PC

              function of one argument.

Note that the set of all PC functions of one argument without any one

          missing is not such a set as it is Recursive.