Re: Perl source filter question

[mjd-perl-pm@plover.com]

> On Fri, Oct 10, 2003 at 01:25:05PM -0400, Mark Dominus wrote:
> > Eric Roode said it was exceptionally difficult to solve this, but that
> > wasn't strong enough.  It is impossible.  There is a mathematical
> > proof that there's no solution; it's called "Rice's theorem".  But the
> > content of the theorem is completely unsurprising: there are no
> > shortcuts to computation; if you want to know the result of computing
> > something, you actually have to compute it.
> 
> It's always interesting to learn something new.  I just learned that the
> Halting Problem has yet another name.

The halting theorem is a special case of Rice's theorem.  The proof is
similar.  

The halting problem theorem says that there is no general way to tell,
by examining a program, whether it will halt on a particular input.

Rice's theorem says that there is no general way to tell, by examining
a program, *any* property of its behavior, unless the property is
completely trivial.  (A property is 'trivial' either if every
program has the property or if no program has the property.)

For example, there's no way to tell whether the program commits an
out-of-bounds array access, or whether it will print the number 17, or
whether it halts on a particular input, or whether it halts on all
inputs, or whether it happens to be a program for computing the square
root function.

-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**