Re:Python code to solve xkcd 1313 by Peter Norvig
by Laremere on Tuesday January 07, 2014 @01:56AM
(#7016059)
Yes, the halting problem can be solved for any programs which can only exist in a finite number of states, but most common definitions of a program would include things such turning machines, which can hold an infinite number of states. Really it comes down to the semantics and bounds of the problem.
However I think the most interesting result is mine :P
So as long as you can show that a program that is not finite in length will not halt in a finite amount of time (I think this is the case, but am not actually positive), I think that a rexex-finding-program-finding-regex should be possible to write, at least in principle (though not in practice).