[TxMt] Re: regexp problem - eternal loop - how to cancel?

[Alaric Snell-Pym]

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