> Because our program just consists of a sequence of regular expressions, you can't loop at all! That, technically, means we can't actually perform Turing Complete But we can do any bounded computation by just unrolling any loops we may have.
Although some (most?) implementations may be. Though by the above quote, the author didn't make use of that.
That's the point, I think: for a large number of real-world algorithms, you don't actually need a Turing Machine. There was a very well-written explanation of this on the front page[1] some time ago, concluded with:
> Any algorithm that can be implemented by a Turing Machine such that its runtime is bounded by some primitive recursive function of input can also be implemented by a primitive recursive function!
Also, "The Little Typer" book explores a language based on "primitive recursive functions" and shows what can be done in it and how.
jamster02|1 year ago
> Because our program just consists of a sequence of regular expressions, you can't loop at all! That, technically, means we can't actually perform Turing Complete But we can do any bounded computation by just unrolling any loops we may have.
Although some (most?) implementations may be. Though by the above quote, the author didn't make use of that.
klibertp|1 year ago
> Any algorithm that can be implemented by a Turing Machine such that its runtime is bounded by some primitive recursive function of input can also be implemented by a primitive recursive function!
Also, "The Little Typer" book explores a language based on "primitive recursive functions" and shows what can be done in it and how.
[1] https://matklad.github.io/2024/08/01/primitive-recursive-fun...