5 ms·

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 arbi

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.

JoshuaDavid 13y 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).
- Laremere 13y 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
- baddox 13y ago
  Or, to make it easier, just put a generous time limit on each program for whatever computer you're running them on.
drdeca 13y 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.
- jakobsen 13y 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
- algorias 13y ago
  It's required to match all such x, otherwise the empty regex "" trivially satisfies the requirement.

JoshuaDavid 13y 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).

Laremere 13y 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
baddox 13y ago
Or, to make it easier, just put a generous time limit on each program for whatever computer you're running them on.

drdeca 13y 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.

jakobsen 13y 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
algorias 13y ago
It's required to match all such x, otherwise the empty regex "" trivially satisfies the requirement.