Next | You can't get there from here | 35 |

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 |