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

[Thomas Allen]

Wow, very informative. I read somewhere that Python prevented infinite
loops, but performing this in IDLE on my office Windows box proved me wrong:

while 1:
    print "Hi"

Thomas Allen

2008/9/8 Alaric Snell-Pym <alaric at snell-pym.org.uk>

> -----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-----
>
> _______________________________________________
> textmate mailing list
> textmate at lists.macromates.com
> http://lists.macromates.com/listinfo/textmate
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macromates.com/textmate/attachments/20080908/61aca172/attachment.html>