Hacker News new | past | comments | ask | show | jobs | submit login
Surprisingly Turing-Complete (gwern.net)
160 points by kushti on Oct 2, 2015 | hide | past | favorite | 61 comments



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?


I don't favour anything that puts more Javascript out there, but I agree with the more general point: if you're going to embed a programming language, better to embed a real, well-designed one than an ad-hoc custom one.

This is also why I find the likes of drools and cucumber utterly wrongheaded. (More generally, there's an antipattern of turing-complete configuration files - often when an organization has convinced itself that "code" needs to go through a long testing and deployment cycle but "configuration" doesn't). If you already have a programming language, use it.


Drools yes, but Cucumber? Cucumber isn't a programming language, it's just a sequence of steps. There's no logic, iteration, calling, etc. There's substitution of table values into steps, but that's no more programming than a mail merge.


Tests end up needing logic, and so Cucumber ends up splitting the flow of a test between two files in different languages.

I should probably have complained about HTML templating that allows a template to call into functions (or have logic in it itself), that's a bigger and clearer example of the problem.

I think the underlying principle here is that the more powerful languages need to be outermost. Having a powerful language call into a weak language to do something that needs to happen safely works well. Having a weak language call into a powerful language just results in a worst of both worlds - all of the danger but less of the power.


How do you feel about Lua?


By the accidents of history I've never actually used it. I've used TCL and Python in similar "embed in C" cases (which worked pretty well); these days I'm mostly on the JVM.


I don't think there's any particular issue (as such) with things being TC. I mean, we've been doing TC DSLs and EDSLs for ages now. As you note, I think the key here is to be disciplined about it. Even though it can be hard, I would probably advocate a sort of gradual approach, but with full-on rewrites/finding a new host language when deemed necessary.

Oh, and I just have to put this in here, because it's so deserving of a meme of its own... Edwin Brady of dependently-typed Idris fame(?) advocates a different and more, IMO, useful term: Pacman Completeness. If you can implement Pacman in $LANGUAGE, it's Turing Complete enough.


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... :-)


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.


At Replicon, a SaaS timesheet provider, we started supporting Python scripting a couple years ago. At first, it was a component of the application we called "pay rules", which are basically the rules that determine how much regular time, over time, double time, etc. an individual is being paid based upon their timesheets. These rules are very different from locale to locale, and at times can be very complex.

The scripting started pretty simple; one script type. It has access to all of our web services, and runs "as the user" but under a specific fixed permission set. The permission set limits the script to read-only services. It is passed simple data: a timesheet reference, and a user. It returns simple data: an array of dates, pay codes, and amounts to be paid. The scripts run under IronPython, so we're able to use .NET's security to prevent the script from accessing the file-system, network, etc. As an additional precaution, the scripts are run on isolated servers that are firewalled to only have network access to the web services servers, and importantly not the database servers or the Internet. Whenever a timesheet is updated, the pay output for that timesheet is marked as "needs recalculation", and the script is executed in a background task.

It was an ugly roll-out. Our first large customer ran into a ton of intermittent errors, which resulted in stale data calculations being used in actual payroll runs. But we fixed these problems quickly, and it's been incredibly smooth after that first month of hell.

And it was very successful. Its success lead to using scripts more and more for other parts of our application, which gives us some incredible per-tenant flexibility while maintaining a single core application. We've followed a few major rules that have helped:

(a) Scripts always do read-only operations; they can never access services that write data. This makes development of the scripts simple because they can be executed with no side-effects, which we leverage in the form of a script simulator that we provide in the UI.

(b) Scripts always have simple inputs, simple outputs. This is tricky every time we create a new type of script. We've found that the less we feed into the script as an input, the more it has to use services to retrieve data, which is actually a fantastically flexible approach. And the same with data output; it needs to contain the results of a calculation, which the script host then does stuff with.

(c) Background execution is far better than interactive execution. We design for background calculations now, making the UI show that "this is being calculated", and preventing certain operations while data is stale. This makes it easy to scale up and down our script servers, and the occasional badly written script doesn't have much of an impact outside of the specific tenant trying to use it.

Overall, the approach IS somewhat crazy. It's a lot more work than just implementing your product the way you want it to work. But for "enterprise customizability", it rocks.


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


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.


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.


Just some more on dependently typed languages: The article actually mentions them in footnote 1. So as it stands, the CSS part really doesn't make sense, because everything written about CSS applies to these dependently typed languages.

In particular, you could write some Agda/Coq/Idris program that implements rule 110, and has some trivial user interaction to repeat this until a stable pattern is reached. This simulates a Turing machine.


> 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.


I don't find it as silly as you do. After all, every programming language needs some physical stuff in the real world to follow the directions the language is encoding. For CSS, there's not a standard runtime, because it's obviously not the intention of CSS. But requiring a human to dumbly follow the rules encoded in this purpose-built CSS is pretty reasonable in this context (which is showing things to be Turing complete which one wouldn't expect to be Turing complete).


With transition:, width:, and :hover, I was able to make an element repeatedly cycle between states with the only user input being to leave a cursor positioned over the page.

Maybe it's a browser-specific quirk; maybe it uses features only implemented after the initial explorations of turing-complete CSS; maybe there isn't any way to hook the two together. CSS will continue to add features over the years, though, and each added feature is another chance to find a missing piece that makes turing-complete CSS easier, more possible, and/or more powerful.


>I'm so tired of "CSS is Turing Complete" meme being propagated.

The article addressed this:

>but the declarations interact with each other just enough to allow an encoding of the cellular automaton Rule 110 (assumption: requires mechanical mouse clicks on the web browser to advance state; see also the Magic: The Gathering example)

[Note: I have omitted links embedded in the original text.]

The claim is not that CSS is Turing-complete, only that it can be used to represent the rules of a Turing-complete automaton. You still need to provide a physical driver.


Rule 110 is so simple that practically everything can represent its rules. You don't need to be Turing complete to do it. Indeed, the rules are even representable in Presburger arithmetic, which, unlike Peano arithmetic, is decidable! You can deduce formulas for every single step of the process, just like with CSS! But I'm sure we can all agree that this is not Turing completeness, otherwise the term itself becomes a farce.


Rule 110 is Turing complete. Therefore anything which can implement/simulate it is also Turing complete.

The same is true of any other model of a Turing machine. If your host computer can simulate a Turing complete machine then the host is also Turing complete.


> You can deduce formulas for every single step of the process, just like with CSS!

You can deduce the formulas, but can you make the formulas self-deducing when driven only by a mechanical clock like a steady mouse-click? Or will it require constant adjustment and intervention by the operator?

> But I'm sure we can all agree that this is not Turing completeness

I'm not sure we can. TC can be tricky. That's why people try to give constructions rather than just claim something or other is TC.


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%2... for proof.


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


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/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.


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_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.


This was (is?) a problem in Minecraft as well, when people were first trying to build CPUs in it.


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

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.


My other favorites are Spacechem (https://www.youtube.com/watch?v=EzzLzUCRmBw) and Terraria.


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


>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.


>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.


Technically speaking, for each program in a TC language we can have a program in a coinductive total language with the same observable behavior.

In nutshell to those who may not be familiar with the field: total languages differ from partial TC languages in that they must always include internally a "hit the reset button" exit from potential infinite loops, and this is enforced by the type system.

Since we can't actually observe an infinite number of program steps even in TC languages, this makes total languages effectively just as powerful as TC ones, but total languages are better-behaved in the sense that we can make a statically enforced distinction between provably terminating and possibly nonterminating code, therefore having all optimization/reasoning benefits in total parts, but also infinite processes in coindutive parts.


Well, I shrug to think about how people would create a program that runs for an indeterminate time (that's most useful ones) in a coinductive total language. Yes, in practice it must be possible.

Then, total languages are just a subset of the non TC languages, and those are as prone to accumulating technical debit as TC languages. For avoiding technical debit, one needs something much less expressive.


Kudos. I wish this point of view was as commonly accepted as you present it.


If it doesn't actually solve the problem you have a non-functional program, not technical debt.


You have a non-functional total functional program.


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.


"Technical default" may be a better name for it.


> Non-turing complete languages are also easier to reason about, less susceptible to bugs and less susceptible to technical debt.

Citation needed. Not my experience at all. Some well-designed total functional languages perhaps, but not non-turing complete languages in general, and not the typical alternatives for configuration and tests.


Have you tried ansible?


Yes, but I don't see the relevance. Ansible is turing-complete, as are all the alternatives in that space AFAIK.


Technically states are turing complete because of the command module but in practice it's as if it weren't.

It's a hell of a lot cleaner than other DSLs, especially puppet's ruby-turing-complete one.


Shrug. Not my experience of it in practice.


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


Indeed. Agda and Coq are excellent examples.


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.


Interesting sub turing complete language:

https://github.com/ainfosec/crema


Another list of "accidentally Turing complete" languages is here:

http://beza1e1.tuxen.de/articles/accidentally_turing_complet...

Edit: Oops, I see this is already linked in the main article as “accidentally Turing-complete”.


My personal contribution is http://demo.robustperception.io:9090/consoles/life.html

Who doesn't want a Turing Complete monitoring language?


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_ru...


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


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?


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.


This was discussed in "Godel, Escher, Bach" in the form of trying to make a record player that can play any record.


TrueType fonts are apparently Turing Complete.


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)


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.


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


It's missing sql !


I guess you missed the mention in the footnote.


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.




Applications are open for YC Summer 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: