Hacker News Reader

Comment by siddboots | Hacker News Reader

"Write the shortest regex that only matches programs that successfully generate the shortest regex given lists of inclusions and exclusions."

View on HN

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.

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

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

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

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.

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

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

Reply on news.ycombinator.com