undefined | Better HN

story

0 pointsJoshuaDavid12y ago0 comments

So long as the unrelated arbitrary program is of finite length, and the regex golfer / arbitrary program composite is running on a machine with a finite amount of state, the halting problem can be solved by running each program for 2^(bits of state) steps or until a state is repeated.

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

0 comments

Laremere12y ago

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

baddox12y ago

Or, to make it easier, just put a generous time limit on each program for whatever computer you're running them on.

j / k navigate · click thread line to collapse

0 comments

Laremere12y ago

However I think the most interesting result is mine :P

baddox12y ago

Or, to make it easier, just put a generous time limit on each program for whatever computer you're running them on.

j / k navigate · click thread line to collapse