9 ms·

Surprisingly Turing-Complete

160 points by kushti 11y ago

chromaton 11y ago
TrueType fonts are apparently Turing Complete.
- umanwizard 11y ago
  In this case it's intentional: they contain embedded bytecode programs for hinting. (That is, adjusting what the font should look like under certain conditions, e.g. low resolution)
tempodox 11y ago
I've got a bunch of spaghetti that are Turing-complete (they form an analog computing machine). I don't even want to think about the security implications.
exDM69 11y ago
Here's a challenge for you guys: Super Mario Maker. It hasn't been proven Turing complete yet, but I'd be surprised if it wasn't. Here's a pointer for you to get started: http://www.gamefaqs.com/boards/805618-super-mario-maker/72515728 http://www.gamefaqs.com/boards/805618-super-mario-maker/7251... This guy says he has built a single nand gate, but hasn't been able to connect several together. As a gamer and a computer scientist, I find Turing complete games intriguing. Minecraft's Redstone is probably intentionally Turing complete, but for example the signalling of trains in OpenTTD probably is not.
- asgard1024 11y ago
  My other favorites are Spacechem (https://www.youtube.com/watch?v=EzzLzUCRmBw https://www.youtube.com/watch?v=EzzLzUCRmBw) and Terraria.
  - thelucky41 11y ago
    Let's not forget Dwarf Fortress, which has several mechanisms that are accidentally turing complete. My favorite is the logic gate using animal behavior. [1] http://dwarffortresswiki.org/index.php/DF2014:Computing http://dwarffortresswiki.org/index.php/DF2014:Computing
- jamesmiller5 11y ago
  If you didn't catch it in the article, it links to a proof of Braid the game's undecidability without use of it's time mechanics. http://arxiv.org/abs/1412.0784 http://arxiv.org/abs/1412.0784 I'd guess Super Mario Maker could be similar if monsters can infinitely spawn, be destroyed and interact with one another, skimming the paper it looks like a requirement.
- panic 11y ago
  One big limitation in Super Mario Maker is that objects too far horizontally offscreen are not simulated and may "de-spawn". Here's a more detailed description of the rules: https://www.reddit.com/r/MarioMaker/comments/3lcrqb/super_mario_maker_science_spawning_despawning_and/ https://www.reddit.com/r/MarioMaker/comments/3lcrqb/super_ma... This means you have to include Mario's position in your design if the device is larger than the horizontal simulation area. Just chaining together NAND gates isn't necessarily enough.
  - steveklabnik 11y ago
    This was (is?) a problem in Minecraft as well, when people were first trying to build CPUs in it.
crdoconnor 11y ago
>Why this effort to make a language in which many programs can’t be written? Because TC is intimately tied to Godel’s incompleteness theorems & Rice’s theorem, allowing TC means that one is forfeiting all sorts of provability properties: in a non-TC language, one may be able to easily prove all sorts of useful things to know; for example, that programs terminate Non-turing complete languages are also easier to reason about, less susceptible to bugs and less susceptible to technical debt. For this reason minimizing as much as possible the amount of turing complete code you write will make your code cleaner. Configuration and tests in particular are usually best described in a non-turing complete language.
- marcosdumay 11y ago
  >Non-turing complete languages are also ... less susceptible to technical debt. Well, except the technical debt of writing all the code in a language that may not support solving your problem once you know it better.
  - crdoconnor 11y ago
    If it doesn't actually solve the problem you have a non-functional program, not technical debt.
    - Moshe_Silnorin 11y ago
      You have a non-functional total functional program.
    - bbrazil 11y ago
      At least in terms of configuration management, what you usually end up with have is a complex config generated by something that is Turing complete. Better to start out and keep the core configuration representation simple (e.g. json, protobuf, ini file) and generated by something powerful like Flabbergast.org.
    - marcosdumay 11y ago
      "Technical default" may be a better name for it.
pjungwir 11y ago
I have taken to calling certain features "Turing Complete" (in a joking-but-not-really way). Most often they are seeking some kind of enterprise customizability: "workflow", survey skip logic, custom reports, white labeling, etc.---basically the same places where you risk falling into the Inner Platform Effect trap. I'm curious how other people tackle requests for these. Usually it starts out with something basic ("email the admin if it's two weeks late", "skip this page if they answer that way", "use the most-recently entered birthday to compute age in years and months", "let people change the logo"), but I can see where it's going. It seems to me you can either field these requests as they come in and get a hodge-podge of strangely-interacting features, or you can build some kind of general-purpose scriptability from the start. (Or you can follow the iPhone and 37 Signals and do it one way only, but often that is not an option.) So I've started to wonder about simply embedding a Javascript interpreter with access to a well-defined API into your application objects. Then people can do whatever they want! Of course this assumes savvy users, perhaps 90% an internal "services" team. But JS is easy to embed, e.g. therubyracer, was designed to be secure (no network/file/shell access), and is the most widely-known of all programming languages. What do other people think? Crazy?
- krupan 11y ago
  Reading your comment reminded me of Steve Yegge's, "The Pinocchio Problem" and also his, "The Universal Design Pattern." How much configurability/programmability should you put into your system is an interesting topic.
- arethuza 11y ago
  Most high end "enterprise" products (CRM, ERP) have entire weird development eco-systems embedded within the product - complete with their own languages, database access mechanisms etc. What I actually find quite interesting about some of these products is the way they are architected to support multiple overlapping customizations from 3rd party vendors, customer specific customizations and the "core" of the application itself. e.g. I've worked on an ERP project that had the base product, customizations within the product, very complex integrations with other systems and over ten 3rd party products that ran on the ERP systems own platform. That was fun... :-)
- 11y ago
Drup 11y ago
It's missing sql !
- simoncion 11y ago
  I guess you missed the mention in the footnote.
btilly 11y ago
My favorite example is SQL. The ANSI-92 standard deliberately made SQL not Turing Complete so that it could be optimized. But people kept adding things to it, like CTE and windowing, and now it is. See http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf http://assets.en.oreilly.com/1/event/27/High%20Performance%2... for proof.
- foobar2020 11y ago
  SQL took off as a way to wrap-up first-order logic over finite models into a form useful for programmers: https://en.wikipedia.org/wiki/Relational_model https://en.wikipedia.org/wiki/Relational_model
amyjess 11y ago
I dug into the CSS example before: it's not actually Turing-complete, but it comes really close. The user still has to manually intervene to advance each iteration of the loop. It would be Turing-complete except for that one little thing, but it's not quite there.
- simoncion 11y ago
  See gwern's rebuttal of this argument: https://news.ycombinator.com/item?id=10320076 https://news.ycombinator.com/item?id=10320076
BrainInAJar 11y ago
So many things are Turing complete for me anyway there's nothing surprising about finding Turing completeness. What I find fascinating is useful languages designed explicitly not to be Turing complete. It's a much harder task
- danghica 11y ago
  Indeed. Agda and Coq are excellent examples.
bbrazil 11y ago
My personal contribution is http://demo.robustperception.io:9090/consoles/life.html http://demo.robustperception.io:9090/consoles/life.html Who doesn't want a Turing Complete monitoring language?
Grue3 11y ago
I'm so tired of "CSS is Turing Complete" meme being propagated. TC is a powerful result with important consequences. Namely the impossibility to solve Halting problem. But CSS is deterministic and a CSS "program" always halts. "But, but, we are making an assumption that a user has to click this particular button until the page doesn't change anymore (assuming infinitely long page [1])" To which I say, poppycock. The purpose of CSS language is to apply styles to the webpage. Once it is processed, the CSS "program" has done it's purpose and is finished (i.e. halted). Running the same CSS "program" over and over again until it consistently produces identical results is not the point of CSS (unlike, say LaTeX/BibTeX compilation process, where you need to compile one file several times to get citation page numbers right, which is Turing complete). You might want to call it something else, like RCSS (repeated CSS). Then, RCSS is Turing complete, but plain CSS isn't. Much like a calculator that can calculate z^2 + C isn't necessarily Turing complete, while a graphical calculator that can draw a Mandelbrot fractal by iterating that formula is. [1] which is acceptable, due to infinite memory assumption of a regular Turing machine
- duaneb 11y ago
  > Namely the impossibility to solve Halting problem. Also the possibility to compute anything possible computing with a turing machine. The fact that you can embed this logic into a style description language accidentally is a meme worth propagating, in my opinion.
- gwern 11y ago
  I don't consider that a remotely relevant argument. CSS is intended to style webpages at all times, webpages which are dynamic; CSS has never had a 'purpose' of rendering once and only once since oh, I don't know, 1997 or so. You might as well object to the _Magic: the Gathering_ example because it assumes a human to play each card mechanically; or you might as well object to the very first Turing machine in Turing's paper because he asks us to assume a setup where it's a human (or 'computer' as they were then known as) following the instructions mechanically.
  - JesperRavn 11y ago
    While I question the tone of the original post, it is correct. The difference between being Turing complete and implementing rule 110 is crucial, and any discussion on the subject needs to make clear that these are not the same. You are obfuscating the role of the driver. In the Turing machine, the driver is part of the Turing machine. In CSS, it is not, and has to be done by the user (or presumably a JS script). As another post by Grue3 points out, almost any language can implement rule 110, including languages that are not Turing complete, and are explicitly said not to be Turing complete in the CS literature/community. For example, Coq, Agda, Idris (with totality checking) and other languages based on Martin Lof type theory, are not Turing complete. That it why they are able to prove totality of their functions. But they can all implement rule 110 with no problem.
moyix 11y ago
Another list of "accidentally Turing complete" languages is here: http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html http://beza1e1.tuxen.de/articles/accidentally_turing_complet... Edit: Oops, I see this is already linked in the main article as “accidentally Turing-complete”.
nutate 11y ago
Interesting sub turing complete language: https://github.com/ainfosec/crema https://github.com/ainfosec/crema
nutate 11y ago
Interesting sub turing complete language: https://github.com/ainfosec/crema https://github.com/ainfosec/crema
mholt 11y ago
Call me naive, but regarding: > why a perfect antivirus program is impossible What does TC have to do with a perfect antivirus program? Does it have something to do with the Halting problem?
- gwern 11y ago
  TC implies there's no such thing as a perfect antivirus program (which detects all and only viruses), or a perfect typechecker etc because if you had such a program, you could turn it into a halting-checker easily: for an AV program, if you want to know if program X halts, you simply put the virus at the end and run the whole thing through your perfect antivirus checker - by assumption, if it detects a virus, then the program X must halt (otherwise the virus would never be able to run and is just dead code) and if it doesn't detect a virus, then program X doesn't halt. Since we know you can't solve the halting problem... In more general terms, this brings us to Rice's theorem.
  - mjcohen 11y ago
    This was discussed in "Godel, Escher, Bach" in the form of trying to make a record player that can play any record.
davidgerard 11y ago
Wikipedia's template language was not intended to be Turing-complete. Then, through some hideous contortions of the syntax, someone managed to construct an "if" statement. This caused so much CPU load they implemented it as a function. And then it evolved into a horrifying accidental DSL, ParserFunctions. They're now trying to rewrite all those clever templates in Lua, having given up avoiding Turing-completeness ... The curse of Turing-completeness is: if you have it, you will soon have to use it.
kzrdude 11y ago
Rust's type system was not meant to be turing complete, yet here we are. Ref: https://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_rusts_type_system_aka_type_system_is/cmkrjz2 https://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_ru...
- kibwen 11y ago
  Alas, the compiler imposes an arbitrary recursion limit that makes the Turing-completeness essentially useless. :)

160 points by kushti 11y ago

chromaton 11y ago

TrueType fonts are apparently Turing Complete.

umanwizard 11y ago
In this case it's intentional: they contain embedded bytecode programs for hinting. (That is, adjusting what the font should look like under certain conditions, e.g. low resolution)

tempodox 11y ago

I've got a bunch of spaghetti that are Turing-complete (they form an analog computing machine). I don't even want to think about the security implications.

exDM69 11y ago

Here's a challenge for you guys: Super Mario Maker. It hasn't been proven Turing complete yet, but I'd be surprised if it wasn't. Here's a pointer for you to get started: http://www.gamefaqs.com/boards/805618-super-mario-maker/72515728 http://www.gamefaqs.com/boards/805618-super-mario-maker/7251... This guy says he has built a single nand gate, but hasn't been able to connect several together. As a gamer and a computer scientist, I find Turing complete games intriguing. Minecraft's Redstone is probably intentionally Turing complete, but for example the signalling of trains in OpenTTD probably is not.

asgard1024 11y ago
My other favorites are Spacechem (https://www.youtube.com/watch?v=EzzLzUCRmBw https://www.youtube.com/watch?v=EzzLzUCRmBw) and Terraria.
- thelucky41 11y ago
  Let's not forget Dwarf Fortress, which has several mechanisms that are accidentally turing complete. My favorite is the logic gate using animal behavior. [1] http://dwarffortresswiki.org/index.php/DF2014:Computing http://dwarffortresswiki.org/index.php/DF2014:Computing
jamesmiller5 11y ago
If you didn't catch it in the article, it links to a proof of Braid the game's undecidability without use of it's time mechanics. http://arxiv.org/abs/1412.0784 http://arxiv.org/abs/1412.0784 I'd guess Super Mario Maker could be similar if monsters can infinitely spawn, be destroyed and interact with one another, skimming the paper it looks like a requirement.
panic 11y ago
One big limitation in Super Mario Maker is that objects too far horizontally offscreen are not simulated and may "de-spawn". Here's a more detailed description of the rules: https://www.reddit.com/r/MarioMaker/comments/3lcrqb/super_mario_maker_science_spawning_despawning_and/ https://www.reddit.com/r/MarioMaker/comments/3lcrqb/super_ma... This means you have to include Mario's position in your design if the device is larger than the horizontal simulation area. Just chaining together NAND gates isn't necessarily enough.
- steveklabnik 11y ago
  This was (is?) a problem in Minecraft as well, when people were first trying to build CPUs in it.

crdoconnor 11y ago

>Why this effort to make a language in which many programs can’t be written? Because TC is intimately tied to Godel’s incompleteness theorems & Rice’s theorem, allowing TC means that one is forfeiting all sorts of provability properties: in a non-TC language, one may be able to easily prove all sorts of useful things to know; for example, that programs terminate Non-turing complete languages are also easier to reason about, less susceptible to bugs and less susceptible to technical debt. For this reason minimizing as much as possible the amount of turing complete code you write will make your code cleaner. Configuration and tests in particular are usually best described in a non-turing complete language.

marcosdumay 11y ago
>Non-turing complete languages are also ... less susceptible to technical debt. Well, except the technical debt of writing all the code in a language that may not support solving your problem once you know it better.
- crdoconnor 11y ago
  If it doesn't actually solve the problem you have a non-functional program, not technical debt.
  - Moshe_Silnorin 11y ago
    You have a non-functional total functional program.
  - bbrazil 11y ago
    At least in terms of configuration management, what you usually end up with have is a complex config generated by something that is Turing complete. Better to start out and keep the core configuration representation simple (e.g. json, protobuf, ini file) and generated by something powerful like Flabbergast.org.
  - marcosdumay 11y ago
    "Technical default" may be a better name for it.

pjungwir 11y ago

I have taken to calling certain features "Turing Complete" (in a joking-but-not-really way). Most often they are seeking some kind of enterprise customizability: "workflow", survey skip logic, custom reports, white labeling, etc.---basically the same places where you risk falling into the Inner Platform Effect trap. I'm curious how other people tackle requests for these. Usually it starts out with something basic ("email the admin if it's two weeks late", "skip this page if they answer that way", "use the most-recently entered birthday to compute age in years and months", "let people change the logo"), but I can see where it's going. It seems to me you can either field these requests as they come in and get a hodge-podge of strangely-interacting features, or you can build some kind of general-purpose scriptability from the start. (Or you can follow the iPhone and 37 Signals and do it one way only, but often that is not an option.) So I've started to wonder about simply embedding a Javascript interpreter with access to a well-defined API into your application objects. Then people can do whatever they want! Of course this assumes savvy users, perhaps 90% an internal "services" team. But JS is easy to embed, e.g. therubyracer, was designed to be secure (no network/file/shell access), and is the most widely-known of all programming languages. What do other people think? Crazy?

krupan 11y ago
Reading your comment reminded me of Steve Yegge's, "The Pinocchio Problem" and also his, "The Universal Design Pattern." How much configurability/programmability should you put into your system is an interesting topic.
arethuza 11y ago
Most high end "enterprise" products (CRM, ERP) have entire weird development eco-systems embedded within the product - complete with their own languages, database access mechanisms etc. What I actually find quite interesting about some of these products is the way they are architected to support multiple overlapping customizations from 3rd party vendors, customer specific customizations and the "core" of the application itself. e.g. I've worked on an ERP project that had the base product, customizations within the product, very complex integrations with other systems and over ten 3rd party products that ran on the ERP systems own platform. That was fun... :-)
11y ago

Drup 11y ago

It's missing sql !

simoncion 11y ago
I guess you missed the mention in the footnote.

btilly 11y ago

My favorite example is SQL. The ANSI-92 standard deliberately made SQL not Turing Complete so that it could be optimized. But people kept adding things to it, like CTE and windowing, and now it is. See http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf http://assets.en.oreilly.com/1/event/27/High%20Performance%2... for proof.

foobar2020 11y ago
SQL took off as a way to wrap-up first-order logic over finite models into a form useful for programmers: https://en.wikipedia.org/wiki/Relational_model https://en.wikipedia.org/wiki/Relational_model

amyjess 11y ago

I dug into the CSS example before: it's not actually Turing-complete, but it comes really close. The user still has to manually intervene to advance each iteration of the loop. It would be Turing-complete except for that one little thing, but it's not quite there.

simoncion 11y ago
See gwern's rebuttal of this argument: https://news.ycombinator.com/item?id=10320076 https://news.ycombinator.com/item?id=10320076

BrainInAJar 11y ago

So many things are Turing complete for me anyway there's nothing surprising about finding Turing completeness. What I find fascinating is useful languages designed explicitly not to be Turing complete. It's a much harder task

danghica 11y ago
Indeed. Agda and Coq are excellent examples.

bbrazil 11y ago

My personal contribution is http://demo.robustperception.io:9090/consoles/life.html http://demo.robustperception.io:9090/consoles/life.html Who doesn't want a Turing Complete monitoring language?

Grue3 11y ago

I'm so tired of "CSS is Turing Complete" meme being propagated. TC is a powerful result with important consequences. Namely the impossibility to solve Halting problem. But CSS is deterministic and a CSS "program" always halts. "But, but, we are making an assumption that a user has to click this particular button until the page doesn't change anymore (assuming infinitely long page [1])" To which I say, poppycock. The purpose of CSS language is to apply styles to the webpage. Once it is processed, the CSS "program" has done it's purpose and is finished (i.e. halted). Running the same CSS "program" over and over again until it consistently produces identical results is not the point of CSS (unlike, say LaTeX/BibTeX compilation process, where you need to compile one file several times to get citation page numbers right, which is Turing complete). You might want to call it something else, like RCSS (repeated CSS). Then, RCSS is Turing complete, but plain CSS isn't. Much like a calculator that can calculate z^2 + C isn't necessarily Turing complete, while a graphical calculator that can draw a Mandelbrot fractal by iterating that formula is. [1] which is acceptable, due to infinite memory assumption of a regular Turing machine

duaneb 11y ago
> Namely the impossibility to solve Halting problem. Also the possibility to compute anything possible computing with a turing machine. The fact that you can embed this logic into a style description language accidentally is a meme worth propagating, in my opinion.
gwern 11y ago
I don't consider that a remotely relevant argument. CSS is intended to style webpages at all times, webpages which are dynamic; CSS has never had a 'purpose' of rendering once and only once since oh, I don't know, 1997 or so. You might as well object to the _Magic: the Gathering_ example because it assumes a human to play each card mechanically; or you might as well object to the very first Turing machine in Turing's paper because he asks us to assume a setup where it's a human (or 'computer' as they were then known as) following the instructions mechanically.
- JesperRavn 11y ago
  While I question the tone of the original post, it is correct. The difference between being Turing complete and implementing rule 110 is crucial, and any discussion on the subject needs to make clear that these are not the same. You are obfuscating the role of the driver. In the Turing machine, the driver is part of the Turing machine. In CSS, it is not, and has to be done by the user (or presumably a JS script). As another post by Grue3 points out, almost any language can implement rule 110, including languages that are not Turing complete, and are explicitly said not to be Turing complete in the CS literature/community. For example, Coq, Agda, Idris (with totality checking) and other languages based on Martin Lof type theory, are not Turing complete. That it why they are able to prove totality of their functions. But they can all implement rule 110 with no problem.

moyix 11y ago

Another list of "accidentally Turing complete" languages is here: http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html http://beza1e1.tuxen.de/articles/accidentally_turing_complet... Edit: Oops, I see this is already linked in the main article as “accidentally Turing-complete”.

nutate 11y ago

Interesting sub turing complete language: https://github.com/ainfosec/crema https://github.com/ainfosec/crema

nutate 11y ago

Interesting sub turing complete language: https://github.com/ainfosec/crema https://github.com/ainfosec/crema

mholt 11y ago

Call me naive, but regarding: > why a perfect antivirus program is impossible What does TC have to do with a perfect antivirus program? Does it have something to do with the Halting problem?

gwern 11y ago
TC implies there's no such thing as a perfect antivirus program (which detects all and only viruses), or a perfect typechecker etc because if you had such a program, you could turn it into a halting-checker easily: for an AV program, if you want to know if program X halts, you simply put the virus at the end and run the whole thing through your perfect antivirus checker - by assumption, if it detects a virus, then the program X must halt (otherwise the virus would never be able to run and is just dead code) and if it doesn't detect a virus, then program X doesn't halt. Since we know you can't solve the halting problem... In more general terms, this brings us to Rice's theorem.
- mjcohen 11y ago
  This was discussed in "Godel, Escher, Bach" in the form of trying to make a record player that can play any record.

davidgerard 11y ago

Wikipedia's template language was not intended to be Turing-complete. Then, through some hideous contortions of the syntax, someone managed to construct an "if" statement. This caused so much CPU load they implemented it as a function. And then it evolved into a horrifying accidental DSL, ParserFunctions. They're now trying to rewrite all those clever templates in Lua, having given up avoiding Turing-completeness ... The curse of Turing-completeness is: if you have it, you will soon have to use it.

kzrdude 11y ago

Rust's type system was not meant to be turing complete, yet here we are. Ref: https://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_rusts_type_system_aka_type_system_is/cmkrjz2 https://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_ru...

kibwen 11y ago
Alas, the compiler imposes an arbitrary recursion limit that makes the Turing-completeness essentially useless. :)