-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 8 Sep 2008, at 2:23 pm, Thomas Allen wrote:
> I know that Python can tell if a loop is infinite, although I'm not
> sure if that behavior applies to Regex (and I can't test it -- I
> couldn't write an infinite search if required...but if you provide
> one, I will). What I mean is that there may be something of
> interest in their source.
It's not infinity that's necessarily the problem; the problem is that
it's possible to write a regexp that takes millions of years to
decide. Which isn't infinite, but is a long time to wait for dinner.
And you can't reliably tell if a loop is infinite. Any automated
test, except in very restricted languages (non Turing-complete ones),
can only classify loops (or any other bit of code into) these three
categories:
- Will loop forever
- Won't loop forever (but might loop for a billion years)
- Might loop forever; who knows?
...and most samples will fall into the latter category, which tells
you no more than you already knew ;-)
What makes you say that Python can tell if a loop is infinite, out of
interest? I'm sure it must be a misinterpretation of something,
unless the halting problem has been solved while I wasn't looking...
http://en.wikipedia.org/wiki/Halting_problem
"In computability theory, the halting problem is a decision problem
which can be stated as follows: given a description of a program and
a finite input, decide whether the program finishes running or will
run forever, given that input.
Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible program-input pairs cannot exist."
ABS
- --
Alaric Snell-Pym
Work: http://www.snell-systems.co.uk/
Play: http://www.snell-pym.org.uk/alaric/
Blog: http://www.snell-pym.org.uk/?author=4
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.8 (Darwin)
iEYEARECAAYFAkjFMq4ACgkQRgz/WHNxCGqy4wCZAdUt2dQXBJrvWZerZ4cdO520
XDIAnjWhygjTS5QnvNQ8M5aOuvoFq+Fm
=hObQ
-----END PGP SIGNATURE-----