3 ms·

It seems to me like he’s cheating in terms of Turing completeness because he has a loop that is running this regex over and over again.

• Hydraulix989 4y ago
  Is it that much of a stretch? {n} in regex for repeated patterns is already a construct, so let n->infinity.
  • still_grokking 4y ago
    Having a `while` loop (or unbounded recursion) is fundamentally more powerful than having only a `for` loop (or similar). https://en.wikipedia.org/wiki/BlooP_and_FlooP https://en.wikipedia.org/wiki/BlooP_and_FlooP So that's a big difference! (Actually the fundamental difference that can make a language Turing-complete in contrast to some other language that doesn't have the possibility to write an infinite loop).
    • Hydraulix989 4y ago
      I'd imagine that regex has no practical use for an infinitely looped pattern, and that's why it was omitted. From an implementation standpoint, it's less of a stretch, but as you point out, it does mean it is now Turing Complete.
  • deleted 4y ago
    [deleted]
• curiousgal 4y ago
  He admits that.