On reductions and undecidability

In this short note, we explore an example of undecidabiolity proof using reductions. We demosntrate explicitly the reduction process by considering the TMs under discussion to be C programs.

A quick reminder

The language

ATM = { < M, w > | M is a TM and M accepts W}

is a caonnoical example of an undecidable language. A large number of reductions to undecidability are done by using this language.

The problem

Define the language L to be

L = {M | M is a TM and L(M) is decidable but not context free}.

Show that L is undecidable by reducing ATM to L. (Do the reduction directly. Do not use Rice's Theorem.)

The Proof

For a given the string (that describes the TM M and an input word w), we build the description < Mw> of the TM defined as follows:

Mw(y):
    If y = an bn cn then
      Accept
    res = Simulate M on w
    Return res


If M accepts w then Mw always accepts. That is L(Mw)=Sigma* in this case. But Sigma* is a regular, decidable and context free language.

If M does not accept w then

L(Mw) = {anbncn | n >= 0},
which is decidable and not context free. Thus Mw in L iff M rejects w and we can use the decider for L in out new decider for ATM.

So, assume for the sake of contradiction that L is decidable, and let IsL(M) be a TM decider for it.

Decider_ATM( < M,w > ):
    compute Mw from < M, w >
    ret = isL( Mw )
    if ( ret == reject ) then
              accept
    else
              reject
Clearly, Decider_ATM is a decider for ATM, which is impossible, since this language is not decidable. As such, our assumption is false, and thus L is undecidable. QED

The reduction done using C programs

To understand this proof, it is important to understand what it means to "compute Mw from < M, w > ". To understand this, let us think about C/C++ programs instead of TM (to remind you, by the Church-Turing hypothesis, what ever a Turing machine can do, a C program can do, and vice versa). So, we are given (the source code) of a program M and an input string w that we would like to run this program on. As concrete example, assume the given program M is the following: 
/* mccarthy.C  */
#include  <stdio.h>

int  mccarthy( int n ) 
{
    if  ( n > 100 )
        return   n - 10;    
    else 
        return  mccarthy( mccarthy( n + 11 ) );
}

int  main()
{
    int  ret, val, count = 0;

    while  ( !feof( stdin ) ) {
        int  ch = fgetc( stdin ); 
        if  ( ch < 0 )    // Check end of input
            break;
        if  ( ch > '\r' )
            count++;
    }   

    val = mccarthy( count );
    printf( "mccarth( %d ) = %d\n", count, val );

    ret = val & 0x1;

    printf( "Returning : %d\n", ret );

    return  ret;
}
/* mccarthy.C - End of File ------------------------------------------*/
(It does not matter for our discussion what this program computes exactly.) The input string we would like to handle is
w=abab.
The program Mw is 
/* mccarthy.C */
#include  <stdio.h>

int  mccarthy( int n ) 
{
    if  ( n > 100 )
        return   n - 10;    
    else 
        return  mccarthy( mccarthy( n + 11 ) );
}

int  old_main()
{
    int  ret, val, count = 0;

    while  ( !feof( stdin ) ) {
        int  ch = fgetc( stdin ); 
        if  ( ch < 0 )    // Check end of input
            break;
        if  ( ch > '\r' )
            count++;
    }   

    val = mccarthy( count );
    printf( "mccarth( %d ) = %d\n", count, val );

    ret = val & 0x1;

    printf( "Returning : %d\n", ret );

    return  ret;
}
/* mccarthy.C - End of File ------------------------------------------*/
#include  <assert.h>

bool  is_a_n__b_n__c_n()
{
    int  count_a = 0, count_b = 0, count_c = 0;
    while  ( !feof( stdin ) ) { 
        int  ch;

        ch = fgetc( stdin );
        if  ( ch < 0 )
            break;
        if  ( ch == 'a' ) {
            count_a++; 
            if  ( ( count_b > 0 )  ||  ( count_c > 0 ) )
                return  false;
        }
        if  ( ch == 'b' ) {
            count_b++; 
            if  (  count_c > 0 ) 
                return  false;
        }
        if  ( ch == 'c' ) 
            count_c++;         
    }
    return  ( count_a == count_b )  &&  ( count_b == count_c );
}
int  run_old_main( const char  * w )
{
    FILE  * fl = fopen( "tmp", "wt" );
    assert( fl != NULL );
    fputs( w, fl );
    fclose( fl );       
    stdin = fopen( "tmp", "rt" );    
    assert( stdin != NULL );
    return  old_main();
}

int  new_main( const char  * w )
{

    if  ( is_a_n__b_n__c_n() ) 
        return  1;
    if  ( run_old_main( w ) == 1 )
        return  1;
    else 
        return  0;
}



int   main()
{
   int  ret = new_main( "abab" );
   printf( "returning  %d\n", ret );
   return  ret;
}
Let us shortly describe what this program is. The first part, is the old program, excpet that we changed main to old_main. Now, the new main calls new_main. The function new_main checks if the input (available on the standard input) is an bn cn. If so, it returns 1. Otherwise, it calls run_old_main with w. run_old_main writes w into a temporary file, and then open it and assign it to stdin. Now, it calls old_main which reading from stdin, will just be reading w. Now, if old_main returns 0 then it returns 1, otherwise it returns 0. Clearly, this program is exactly Mw.

So, computing < Mw > from < M, w > is no more than taking the C program for M and the string w and generating the above (new) C program. How can this be done? Well, it really no more than copying the original C program, renaming the main procedure to old_main, and then adding some extra code. This can be easily done. Indeed, one can write a C program that does exactly that.
Here is the C source of rewrite_program.C - the program computing Mw from M and w.

In our case:
  1. the input program M is mccarthy.C
  2. Input string: w = "abab".
  3. And the resulting program Mw is mccarthy_abab.C.
  4. The conversion was done by compiling rewrite_program.C and executing:
    ./rewrite_program mccarthy.C abab mccarthy_abab.C

The key point...

The key observation here is that we computed the program mccarthy_abab.C (i.e., Mw) from mccarthy.C (i.e., M) and w without understanding what the program mccarthy.C really does. This conversion process is just a simple string manipulation process. In particular, in no point during the generation of mccarthy_abab.C did we run the program mccarthy.C on the input w! In fact, it is not even obvious on first look on mccarthy.C that it stops at all!

Another example

  1. the input program M is even.C
  2. Input string: w = "abab".
  3. And the resulting program Mw is even_abab.C.
  4. The conversion was done by compiling rewrite_program.C and executing:
    ./rewrite_program even.C abab even_abab.C
Last modified: Fri May 8 14:32:55 CDT 2009