Squares

        sub calculates_squares {
          my $code = shift;
          ... returns true if and only if $code is a function
              for computing squares ...
        }

• Why can't we write this?

• Because if we could write calculates_squares, we could use it to write this:

        sub halts {
          my ($source_code, $input) = @_;
          my $newcode = 'sub { my $n = shift;
                                my $f = eval "CODE";
                                $f->("INPUT");
                                return $n * $n;
                               }';
          $newcode =~ s/CODE/$source_code/;
          $newcode =~ s/INPUT/$input/;
          return calculates_squares($newcode);
        }        

• $newcode is a program to calculate squares...

  • But only if the call $f->("...") would halt

• If we could recognize squaring functions, we could recognize halting functions too

• We can't recognize halting functions

• Therefore, we can't recognize squaring functions

Next

Copyright © 2005 M. J. Dominus