The flip side is that if the program takes untrusted input, Turing-completeness creates a weird machine -- a way for attackers to run code on your machine.
It’s very easy to make a string rewriting system accidentally Turing complete. All you need is iterated rewriting with a sufficiently flexible rewrite system: regexes are the classic example, but they are overpowered as this Curl example illustrates. Universities should teach that Turing completeness is not at all magical, but in fact quite difficult to avoid.
Who needs regexps when literal substring replacements are enough (also a classical example)! Like regexps and unlike counter machines, it is even mutually polynomially reducible with Turing machines, RAM machines, etc.
gignico | a day ago
I love accidental Turing-completeness, I find it poetic somehow.
andyc | 18 hours ago
The flip side is that if the program takes untrusted input, Turing-completeness creates a weird machine -- a way for attackers to run code on your machine.
Also: https://sergey.cs.dartmouth.edu/wm/
Although now I see there is a good distinction between being able to run arbitrary code, and exploitability: https://www.dullien.net/thomas/weird-machines-exploitability.pdf (2017)
gignico | 16 hours ago
Yes of course being poetic doesn’t make it desirable in a system :)
AshkanKiani | 6 hours ago
Normalize deploying poetry machines and not programs
pert | 22 hours ago
When will we see doom running in curl 8.16
fanf | 17 hours ago
It’s very easy to make a string rewriting system accidentally Turing complete. All you need is iterated rewriting with a sufficiently flexible rewrite system: regexes are the classic example, but they are overpowered as this Curl example illustrates. Universities should teach that Turing completeness is not at all magical, but in fact quite difficult to avoid.
k749gtnc9l3w | 14 hours ago
Who needs regexps when literal substring replacements are enough (also a classical example)! Like regexps and unlike counter machines, it is even mutually polynomially reducible with Turing machines, RAM machines, etc.