8 ms·

Accidentally Turing-Complete

148 points by sebastialonso 6y ago

arunc 6y ago
Reminded me of the fact that D templates are not Turning Complete.
- FeepingCreature 6y ago
  As a D user, I highly doubt that, considering we had raytracers written in templates fourteen years and one major language version ago. [1] What stops them? [1] http://h3.gd/posts/ctrace/ http://h3.gd/posts/ctrace/
- ben-schaaf 6y ago
  IIRC D templates are more powerful than C++ templates, and certainly turning complete. CTFE is also turning complete.
anderskaseorg 6y ago
This list is careful to mention that the PowerPoint machine requires the user to perform an action for each step, but neglects to make the same disclaimer for the HTML5 + CSS3 machine.
- SQueeeeeL 6y ago
  I thought HTML5 was just a single button click.
  - Dylan16807 6y ago
    The version that's linked requires a button press for each colored box.
kbumsik 6y ago
Also x86 mov instruction is Turing complete! [1] There is a guy who run Doom with only mov instructions, but it is of course incredibly slow, one frame every 7 hours :) [2] [1]: https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312 [2]: https://news.ycombinator.com/item?id=16218872 https://news.ycombinator.com/item?id=16218872
- xxs 6y ago
  I wonder how that one was missed as it's a famous example.
asplake 6y ago
How concerned should we be that BGP is in there?
k_sze 6y ago
The game "Cities: Skylines" is also Turing-complete: https://medium.com/@balidani/cities-skylines-is-turing-complete-e5ccf75d1c3a https://medium.com/@balidani/cities-skylines-is-turing-compl...
- Medox 6y ago
  Factorio too. Raycasting engine: https://www.youtube.com/watch?v=7lVAFcDX4eM https://www.youtube.com/watch?v=7lVAFcDX4eM
  - PythagoRascal 6y ago
    And "Baba Is You": https://twitter.com/mattar0d/status/1109987662608384000 https://twitter.com/mattar0d/status/1109987662608384000
moreati 6y ago
I'm still not sure if Python Pickles, without the GLOBAL opcode to call into Python, are Turing complete. Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-gl... https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great. My research/tinkering so far is https://github.com/moreati/pickle-fuzz https://github.com/moreati/pickle-fuzz
- bugmen0t 6y ago
  Pickle is a stack machine (https://en.wikipedia.org/wiki/Stack_machine https://en.wikipedia.org/wiki/Stack_machine). It is Turing complete. See source code and documentation at https://github.com/python/cpython/blob/master/Lib/pickle.py#L107and https://github.com/python/cpython/blob/master/Lib/pickle.py#... https://github.com/python/cpython/blob/master/Lib/pickletools.py#L38 https://github.com/python/cpython/blob/master/Lib/pickletool... N.B: "Turing complete" really means a lot less than you seem to believe.
  - Dylan16807 6y ago
    A machine that has a stack and runs a series of instructions in sequence, no looping or branching, is a pushdown automaton. That's significantly weaker than Turing complete. (A pushdown automaton can do branching if it wants, but the lack of looping / going left is critical.)
malkia 6y ago
But most importantly - should your config language be turing complete, or not - or do we care or not?
- AgentME 6y ago
  If a config file isn't deterministic (because it's executable and can read info from its environment), then it can be harder for tools to introspect on the full config (imagine an IDE showing your project's settings or a tool that validates it; the tool would be blind to what your config specifies in environments the tool doesn't test with) or know when it's safe to cache the config's result (because the tool doesn't necessarily know whether the environment may have changed in a way the config cares about). (Extreme example: if you had a software library that declared its list of dependencies in an executable config file, and that config file could arbitrarily read the environment, maybe toggling certain dependencies depending on your platform and whether you had certain pre-requisites on your system, then a package repository that the library is published on can't show a canonical list of the library's dependencies. When a user wants to install the library and its dependencies, the package repository server can't respond with library and its dependencies together, because the library's dependencies for you could only be found out by executing its executable dependency config on your computer specifically, so the server would need to send you the library, your computer would need run the dependency config, and then go back and ask the server for the dependencies, and then repeat for their depedencies, etc.) Also, executable config files (deterministic or not) aren't so easy or pretty to programmatically modify. If the config file can define arbitrary functions and use them to compute the config, then if you want to tweak the config with a tool like an IDE or package manager, then it will need to try to recognize a pattern in the config file, or add a chunk of code at the bottom that just mutates the config file after your handwritten code.
- shawnz 6y ago
  Note that even if you believe in using a DSL for configuration, there are still options that are not turing-complete, like Bazel's Starlark
- ajuc 6y ago
  It shouldn't be turing-complete, because merging code is hard, and merging configurations is useful.
janzer 6y ago
While rather more dense, I find Gwern's article/list[1] a bit more extensive (although missing a few from this list), while also having some interesting commentary on security implications. [1] https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete
krick 6y ago
Somebody should make awesome-turing-complete project on github, so we can merge everything from the comments here into a neat list...
- abetusk 6y ago
  Done [1] [1] https://github.com/abetusk/Awesome-Turing-Machine-Equivalence https://github.com/abetusk/Awesome-Turing-Machine-Equivalenc...
xurukefi 6y ago
It's pretty hard to make something that is not turing-complete. I've always wondered if it wouldn't be beneficial to have a turing-incomplete language given that Rice's theorem then doesn't necessarily hold and thus very powerful semantic analysis might be possible. But the language is then probably not practical due to limited expressiveness.
- gpderetta 6y ago
  Total Functional Programming is a thing [1]. [1] https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming
- marcosdumay 6y ago
  There is Dhall (https://dhall-lang.org/ https://dhall-lang.org/). The overall loss of expressiveness is surprisingly small, but the number of details you have to work around is annoying.
- jefftk 6y ago
  If you have a VM that processes opcodes and has no way of (a) adding opcodes to the end or (b) moving backwards in the stream, it won't be Turing complete. I've used a scripting system for a server that was intentionally written this way to bound the harm a misbehaving script could have on the server. RE2 is also designed along these lines https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html
- 6gvONxR4sf7o 6y ago
  Agreed. It's still just a hypothesis that interesting computing is equivalent to a turing machine and I don't buy it. For basically every program I've built, I could (hypothetically, bugs aside) either prove that it terminates, or it's a program like (forever do "something i can prove terminates"). The space of programs that we actually use seems kinda small. Designing a computing model that only covers what's useful while also making it convenient appears to be a long standing open problem. I'm sooooo curious to see things happen there.
  - 6y ago
FartyMcFarter 6y ago
On Magic The Gathering being Turing-complete, this is an interesting quote: > Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. At first I thought this was pretty mind-blowing for a game, but actually this is directly comparable with a Turing machine; each step is forced, mechanical and very easy to derive, and yet, the overall behaviour is generally undecidable.
- lukifer 6y ago
  For anyone curious about the details of building a Turing machine in MtG, Because Science did a thorough breakdown and demonstration, using actual cards: https://youtu.be/pdmODVYPDLA https://youtu.be/pdmODVYPDLA
Hitton 6y ago
>In a very similar fashion to C++, the type system of TypeScript can be used to implement a prime check. PCRE can do that too (for numbers in unary). https://www.masteringperl.org/2013/06/how-abigails-prime-number-checker-works/ https://www.masteringperl.org/2013/06/how-abigails-prime-num...
waynecochran 6y ago
Turing Complete is not a very high bar. Add a second stack to a pushdown automata and its Turing Complete. Add two counters to a NFA and it’s Turing Complete. I am not sure if folks know what this means.
- codeflo 6y ago
  Yes. Judging from the HN discussion of a very similar list a week ago, a loud minority confuses “not Turing complete” with “sandboxed”. Hence lots of discussions about security that seem to miss the point.
ViViDboarder 6y ago
Oh hey, the Vim example is my project. Super fun to build.
Dylan16807 6y ago
> HTML5 + CSS3 Nope. I'm going to argue this every time I see it. It only demonstrates basic arithmetic. When an external actor has to come along and take each iteration's output and manually do things with it, you don't have Turing completeness.
- dddbbb 6y ago
  I agree, I also think there is some weirdness going on with the 'we can presume it has infinite memory'. There seems to be many assumptions of different strength all waved with that same phrase, depending on the system in question.
  - htfu 6y ago
    Without that presumption how could anything ever be considered Turing complete? If you're simulating something with infinite memory you get to pretend you have infinite memory. Feasibility has already been suspended. Edit: ok I get it. Still, GP observation is hardly at that level from my (limited) perspective. Not being able to advance by itself means it's not a standalone system - otoh external actor is obviously implicit for many other examples as well. I suppose they (and me) are taking the word machine too literally. But "pens are Turing-complete" seems a bit, well, diluted.
- a1369209993 6y ago
  That is clearly a demonstration of Turing completeness, but it's a demonstration of Turing completeness of HTML5 + CSS3 + copying from output back to input (the same as eg string rewriting systems) and that could stand to be stated more clearly.
  - Dylan16807 6y ago
    Technically yes, but only when it's paired with the understanding that arithmetic plus copying the output back to input is Turing complete. HTML5+CSS is only supplying the arithmetic half of the equation.
numpad0 6y ago
That Pokémon is an arbitrary code execution, not “accidentally turning complete”
- FartyMcFarter 6y ago
  But if a system allows code execution on its host CPU, and the host CPU is Turing complete, this means the system itself is Turing complete too by extension.
NwtnsMthd 6y ago
Turns out Pokemon Yellow is also Turing complete! This fantastic hack escapes the game, loads a couple bootstrapping sequences and then proceeds to turn Pokemon into a MIDI player. http://aurellem.org/vba-clojure/html/total-control.html http://aurellem.org/vba-clojure/html/total-control.html
- Dylan16807 6y ago
  * using an enormous glitch. It's really cool, but it's notably different from using actual ingame mechanics to compute. And there are much more fun versions of pokemon yellow total control than the link you and the article have. https://www.youtube.com/watch?v=zZCqoHHtovQ https://www.youtube.com/watch?v=zZCqoHHtovQ
favorited 6y ago
The C++ templates example is kind of a meme, and Bjarne has pushed back on the idea that it was "accidental." Sure, they didn't set out saying "we want to design a Turing-complete generics system" (because what kind of problem statement is that?), but templates were explicitly designed to be as general-purpose as possible. Turing-completeness was the result of that design goal: "...I had aimed for generalty (and gotten Turing completeness modulo translation limits). I opposed restrictions to C++ immediately when Erwin Unruh presented what is widely believed to be the first template metaprogram to the ISO Standards committee's evolution working group." http://www.stroustrup.com/bs_faq.html#understand http://www.stroustrup.com/bs_faq.html#understand

148 points by sebastialonso 6y ago

arunc 6y ago

Reminded me of the fact that D templates are not Turning Complete.

FeepingCreature 6y ago
As a D user, I highly doubt that, considering we had raytracers written in templates fourteen years and one major language version ago. [1] What stops them? [1] http://h3.gd/posts/ctrace/ http://h3.gd/posts/ctrace/
ben-schaaf 6y ago
IIRC D templates are more powerful than C++ templates, and certainly turning complete. CTFE is also turning complete.

anderskaseorg 6y ago

This list is careful to mention that the PowerPoint machine requires the user to perform an action for each step, but neglects to make the same disclaimer for the HTML5 + CSS3 machine.

SQueeeeeL 6y ago
I thought HTML5 was just a single button click.
- Dylan16807 6y ago
  The version that's linked requires a button press for each colored box.

kbumsik 6y ago

Also x86 mov instruction is Turing complete! [1] There is a guy who run Doom with only mov instructions, but it is of course incredibly slow, one frame every 7 hours :) [2] [1]: https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312 [2]: https://news.ycombinator.com/item?id=16218872 https://news.ycombinator.com/item?id=16218872

xxs 6y ago
I wonder how that one was missed as it's a famous example.

asplake 6y ago

How concerned should we be that BGP is in there?

k_sze 6y ago

The game "Cities: Skylines" is also Turing-complete: https://medium.com/@balidani/cities-skylines-is-turing-complete-e5ccf75d1c3a https://medium.com/@balidani/cities-skylines-is-turing-compl...

Medox 6y ago
Factorio too. Raycasting engine: https://www.youtube.com/watch?v=7lVAFcDX4eM https://www.youtube.com/watch?v=7lVAFcDX4eM
- PythagoRascal 6y ago
  And "Baba Is You": https://twitter.com/mattar0d/status/1109987662608384000 https://twitter.com/mattar0d/status/1109987662608384000

moreati 6y ago

I'm still not sure if Python Pickles, without the GLOBAL opcode to call into Python, are Turing complete. Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-gl... https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great. My research/tinkering so far is https://github.com/moreati/pickle-fuzz https://github.com/moreati/pickle-fuzz

bugmen0t 6y ago
Pickle is a stack machine (https://en.wikipedia.org/wiki/Stack_machine https://en.wikipedia.org/wiki/Stack_machine). It is Turing complete. See source code and documentation at https://github.com/python/cpython/blob/master/Lib/pickle.py#L107and https://github.com/python/cpython/blob/master/Lib/pickle.py#... https://github.com/python/cpython/blob/master/Lib/pickletools.py#L38 https://github.com/python/cpython/blob/master/Lib/pickletool... N.B: "Turing complete" really means a lot less than you seem to believe.
- Dylan16807 6y ago
  A machine that has a stack and runs a series of instructions in sequence, no looping or branching, is a pushdown automaton. That's significantly weaker than Turing complete. (A pushdown automaton can do branching if it wants, but the lack of looping / going left is critical.)

malkia 6y ago

But most importantly - should your config language be turing complete, or not - or do we care or not?

AgentME 6y ago
If a config file isn't deterministic (because it's executable and can read info from its environment), then it can be harder for tools to introspect on the full config (imagine an IDE showing your project's settings or a tool that validates it; the tool would be blind to what your config specifies in environments the tool doesn't test with) or know when it's safe to cache the config's result (because the tool doesn't necessarily know whether the environment may have changed in a way the config cares about). (Extreme example: if you had a software library that declared its list of dependencies in an executable config file, and that config file could arbitrarily read the environment, maybe toggling certain dependencies depending on your platform and whether you had certain pre-requisites on your system, then a package repository that the library is published on can't show a canonical list of the library's dependencies. When a user wants to install the library and its dependencies, the package repository server can't respond with library and its dependencies together, because the library's dependencies for you could only be found out by executing its executable dependency config on your computer specifically, so the server would need to send you the library, your computer would need run the dependency config, and then go back and ask the server for the dependencies, and then repeat for their depedencies, etc.) Also, executable config files (deterministic or not) aren't so easy or pretty to programmatically modify. If the config file can define arbitrary functions and use them to compute the config, then if you want to tweak the config with a tool like an IDE or package manager, then it will need to try to recognize a pattern in the config file, or add a chunk of code at the bottom that just mutates the config file after your handwritten code.
shawnz 6y ago
Note that even if you believe in using a DSL for configuration, there are still options that are not turing-complete, like Bazel's Starlark
ajuc 6y ago
It shouldn't be turing-complete, because merging code is hard, and merging configurations is useful.

janzer 6y ago

While rather more dense, I find Gwern's article/list[1] a bit more extensive (although missing a few from this list), while also having some interesting commentary on security implications. [1] https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete

krick 6y ago

Somebody should make awesome-turing-complete project on github, so we can merge everything from the comments here into a neat list...

abetusk 6y ago
Done [1] [1] https://github.com/abetusk/Awesome-Turing-Machine-Equivalence https://github.com/abetusk/Awesome-Turing-Machine-Equivalenc...

xurukefi 6y ago

It's pretty hard to make something that is not turing-complete. I've always wondered if it wouldn't be beneficial to have a turing-incomplete language given that Rice's theorem then doesn't necessarily hold and thus very powerful semantic analysis might be possible. But the language is then probably not practical due to limited expressiveness.

gpderetta 6y ago
Total Functional Programming is a thing [1]. [1] https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming
marcosdumay 6y ago
There is Dhall (https://dhall-lang.org/ https://dhall-lang.org/). The overall loss of expressiveness is surprisingly small, but the number of details you have to work around is annoying.
jefftk 6y ago
If you have a VM that processes opcodes and has no way of (a) adding opcodes to the end or (b) moving backwards in the stream, it won't be Turing complete. I've used a scripting system for a server that was intentionally written this way to bound the harm a misbehaving script could have on the server. RE2 is also designed along these lines https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html
6gvONxR4sf7o 6y ago
Agreed. It's still just a hypothesis that interesting computing is equivalent to a turing machine and I don't buy it. For basically every program I've built, I could (hypothetically, bugs aside) either prove that it terminates, or it's a program like (forever do "something i can prove terminates"). The space of programs that we actually use seems kinda small. Designing a computing model that only covers what's useful while also making it convenient appears to be a long standing open problem. I'm sooooo curious to see things happen there.
- 6y ago

FartyMcFarter 6y ago

On Magic The Gathering being Turing-complete, this is an interesting quote: > Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. At first I thought this was pretty mind-blowing for a game, but actually this is directly comparable with a Turing machine; each step is forced, mechanical and very easy to derive, and yet, the overall behaviour is generally undecidable.

lukifer 6y ago
For anyone curious about the details of building a Turing machine in MtG, Because Science did a thorough breakdown and demonstration, using actual cards: https://youtu.be/pdmODVYPDLA https://youtu.be/pdmODVYPDLA

Hitton 6y ago

>In a very similar fashion to C++, the type system of TypeScript can be used to implement a prime check. PCRE can do that too (for numbers in unary). https://www.masteringperl.org/2013/06/how-abigails-prime-number-checker-works/ https://www.masteringperl.org/2013/06/how-abigails-prime-num...

waynecochran 6y ago

Turing Complete is not a very high bar. Add a second stack to a pushdown automata and its Turing Complete. Add two counters to a NFA and it’s Turing Complete. I am not sure if folks know what this means.

codeflo 6y ago
Yes. Judging from the HN discussion of a very similar list a week ago, a loud minority confuses “not Turing complete” with “sandboxed”. Hence lots of discussions about security that seem to miss the point.

ViViDboarder 6y ago

Oh hey, the Vim example is my project. Super fun to build.

Dylan16807 6y ago

> HTML5 + CSS3 Nope. I'm going to argue this every time I see it. It only demonstrates basic arithmetic. When an external actor has to come along and take each iteration's output and manually do things with it, you don't have Turing completeness.

dddbbb 6y ago
I agree, I also think there is some weirdness going on with the 'we can presume it has infinite memory'. There seems to be many assumptions of different strength all waved with that same phrase, depending on the system in question.
- htfu 6y ago
  Without that presumption how could anything ever be considered Turing complete? If you're simulating something with infinite memory you get to pretend you have infinite memory. Feasibility has already been suspended. Edit: ok I get it. Still, GP observation is hardly at that level from my (limited) perspective. Not being able to advance by itself means it's not a standalone system - otoh external actor is obviously implicit for many other examples as well. I suppose they (and me) are taking the word machine too literally. But "pens are Turing-complete" seems a bit, well, diluted.
a1369209993 6y ago
That is clearly a demonstration of Turing completeness, but it's a demonstration of Turing completeness of HTML5 + CSS3 + copying from output back to input (the same as eg string rewriting systems) and that could stand to be stated more clearly.
- Dylan16807 6y ago
  Technically yes, but only when it's paired with the understanding that arithmetic plus copying the output back to input is Turing complete. HTML5+CSS is only supplying the arithmetic half of the equation.

numpad0 6y ago

That Pokémon is an arbitrary code execution, not “accidentally turning complete”

FartyMcFarter 6y ago
But if a system allows code execution on its host CPU, and the host CPU is Turing complete, this means the system itself is Turing complete too by extension.

NwtnsMthd 6y ago

Turns out Pokemon Yellow is also Turing complete! This fantastic hack escapes the game, loads a couple bootstrapping sequences and then proceeds to turn Pokemon into a MIDI player. http://aurellem.org/vba-clojure/html/total-control.html http://aurellem.org/vba-clojure/html/total-control.html

Dylan16807 6y ago
* using an enormous glitch. It's really cool, but it's notably different from using actual ingame mechanics to compute. And there are much more fun versions of pokemon yellow total control than the link you and the article have. https://www.youtube.com/watch?v=zZCqoHHtovQ https://www.youtube.com/watch?v=zZCqoHHtovQ

favorited 6y ago

The C++ templates example is kind of a meme, and Bjarne has pushed back on the idea that it was "accidental." Sure, they didn't set out saying "we want to design a Turing-complete generics system" (because what kind of problem statement is that?), but templates were explicitly designed to be as general-purpose as possible. Turing-completeness was the result of that design goal: "...I had aimed for generalty (and gotten Turing completeness modulo translation limits). I opposed restrictions to C++ immediately when Erwin Unruh presented what is widely believed to be the first template metaprogram to the ISO Standards committee's evolution working group." http://www.stroustrup.com/bs_faq.html#understand http://www.stroustrup.com/bs_faq.html#understand