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.

In reply to Re^2: regex step counting (Halting problem) by Corion
in thread regex step counting by Random_Walk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.