Observation: Any piece of software/service or piece of software/service used in a software/service chain which implements and/or consumes Regular Expressions (aka RE's, RegExp's) -- is potentially Turing Complete, and should be audited for Turing completeness if security in that context is a concern...
back
1 comments
Speaking strictly, the original definition of Regex required only a finite state machine with zero stacks.
You need 2 stacks for Turing completeness.
Tho a lot of regex libraries can support much more than just “regex”
>"You need 2 stacks for Turing completeness."
I am not completely sure about that assertion...
We know that Rule 110 is Turing complete:
https://en.wikipedia.org/wiki/Rule_110
>"Rule 110 with a particular repeating background pattern is known to be Turing complete.[2]"
So if Rule 110 = Turing completeness, then we could either prove Turing completeness by proving Turing completeness OR we could prove Turing completeness by proving Rule 110 equivalence...
Next we have Markov algorithms:
https://en.wikipedia.org/wiki/Markov_algorithm
>"a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols.
Markov algorithms have been shown to be Turing-complete
, which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation."
(Note that Markov algorithms do not use stacks (nor do Turing machines, nor does Rule 110, nor do stackless "Turing tarpit" esoteric languages, nor does Langton's Ant or other Turing complete cellular automata).)
RegExp's are basically a "string rewriting system that uses grammar-like rules to operate on strings of symbols"
So if a such a string rewriting system used in conjunction with a Regular Expression functionality can be proved to be a Markov algorithm, then we have automatic proof that it is also Turing complete, with no need for stacks!
Why not read the following:
Simplest Turing-complete ruleset for Markov algorithm
https://cs.stackexchange.com/questions/44717/simplest-turing...
And possibly this:
https://esolangs.org/wiki/Nopfunge
>"Nopfunge is a fungeoid designed by Hubert Lamontagne in 2015. It is a two-dimensional esoteric programming language based on a severely restricted subset of the well known Befunge language. Its goal is to show that having access to a sufficiently flexible program geometry is indeed the only thing that is needed to achieve Turing completeness."
[...]
>"The ONLY valid commands in Nopfunge are the PC direction change commands < > v ^ and empty space (which are the same as in Befunge). This means that Nopfunge has no stack, no numbers and no conditionals: there are
NO stack manipulation commands
and NO commands to store or retrieve data from the program grid. There are no variables or data storage or functions or objects of any kind. The ONLY thing that ever happens in Nopfunge is PC movement.
In spite of this, Nopfunge is Turing complete."
Point is: If it were me, and I were designing a system, then I'd be highly careful (perhaps "circumspect" is a better word) about code that implements or evaluates, produces or consumes Regular Expressions (or implements any text rewrite rules for that matter!) if the system which that code was to be part of, was intended to be as secure as possible...
> >"You need 2 stacks for Turing completeness."
> I am not completely sure about that assertion...
What GP means is that a finite state machine is not Turing-complete, and neither is a finite state machine with a single stack (pushdown automaton / stack automation).
Piet is another near-exception to this -- the language only has a single "stack" but the "stack" is equipped with a 'roll' operation that cannot be implemented with a proper stack and O(1) memory.
> do not use stacks (nor do Turing machines
A Turing machine has two stacks. They're the part of the tape to the left of the head and the part of the tape to the right of the head.
The other Turing complete systems described use arbitrarily large amounts of storage that are addressed more often, and for example Langton's Ant uses a two-dimensional tape, which is "not two stacks" in the sense that it is more complex than two stacks.
More complex how? Both are abstract and can simulate each other. The difference in complexity would wend into practicality arguments that don't apply in Turing world.
Turing machine uses a tape, which is equivalent to two stacks, and also equivalent to a 2-dimensional tape (Farey Sequence), and (I guess, per previous comment) equivalent to Rule 110.
The word "Equivalent" always carries some load, though. For example, the Langton Ant tape and Rule 110 use a more interesting version of "blank" initial state, similar to the "send a message by flipping a coin on a chess board with an arbitrarily flipped coin on each square" puzzle.