laziness, impatience, and hubris | |
PerlMonks |
Re: Halting problem? Sheesh, I hope not.by demerphq (Chancellor) |
on Jan 19, 2005 at 22:01 UTC ( [id://423520]=note: print w/replies, xml ) | Need Help?? |
Well if it isnt the the halting problem exactly i suspect its damn near as hard. How about these two:
I suspects its a lot easier to show that regex E can produce something that regex R wont accept, but saying for sure that R will accept all patterns producable by E isnt so easy. And IMO neither are approachable problems at all. Id be thinking of alternate solutions. One possibility is to produce something that generates random data from the E pattern and then hammer the R pattern with the products to see but obviously this wont be a proof, just a strong argument. /me wonders if he still has his data from regex code...
--- demerphq
In Section
Seekers of Perl Wisdom
|
|