You don't need to solve the halting problem to enforce and/or check that a regex stops after a time limit or step limit.

If you're launching the regex engine with user-supplied input, I'm not sure whether you can single-step through the regexp, but most likely you can do something like what Regexp::Debugger does and limit the amount of steps there.

Alternatively, declare an upper time limit which you allow for user-supplied regular expressions.

The problematic part of the halting problem only comes into play for stuff that runs very long but not infinitely long. For the OP, these two cases fall into the same category.