undefined | Better HN

0 pointsLaremere12y ago0 comments

Such a regex cannot exist:

1. Take an existing solution to finding the shortest regex given a list of inclusions an exclusions.

2. Take another unrelated arbitrary program.

3. Combine the two, when the arbitrary program terminates, use the existing solution to solve the problem.

4. Such a regex would have to solve the halting problem to know if the arbitrary program terminates and the existing solution solves the problem.

5. Since the halting problem cannot be solved, no such regex can exist.

0 comments

JoshuaDavid12y ago

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

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

drdeca12y ago

If a regex is required to only match x if p(x), is the regex required to match ALL x such that p(x)?

Although this is probably just pointless nitpicking on my part.

jakobsen12y ago

Of course it is required (within the computational limits of your computer, of course)

If p(x) means 'x is an integer', you could use the regex /^1$/ since it matches integers only (in particular, the integer 1). That's not sufficient, you need to match all integers.

edited:format

algorias12y ago

It's required to match all such x, otherwise the empty regex "" trivially satisfies the requirement.

j / k navigate · click thread line to collapse