-----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