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.
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.
> 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.
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.
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.
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.
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.
>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 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.
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
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.
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.
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.
[+] [-] pjungwir|10 years ago|reply
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?
[+] [-] lmm|10 years ago|reply
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.
[+] [-] lomnakkus|10 years ago|reply
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.
[+] [-] arethuza|10 years ago|reply
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... :-)
[+] [-] krupan|10 years ago|reply
[+] [-] mfenniak|10 years ago|reply
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.
[+] [-] Grue3|10 years ago|reply
"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
[+] [-] gwern|10 years ago|reply
[+] [-] duaneb|10 years ago|reply
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.
[+] [-] baddox|10 years ago|reply
[+] [-] Uristqwerty|10 years ago|reply
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.
[+] [-] jsprogrammer|10 years ago|reply
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.
[+] [-] btilly|10 years ago|reply
See http://assets.en.oreilly.com/1/event/27/High%20Performance%2... for proof.
[+] [-] foobar2020|10 years ago|reply
[+] [-] exDM69|10 years ago|reply
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.
[+] [-] panic|10 years ago|reply
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.
[+] [-] jamesmiller5|10 years ago|reply
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.
[+] [-] asgard1024|10 years ago|reply
[+] [-] crdoconnor|10 years ago|reply
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|10 years ago|reply
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.
[+] [-] lmm|10 years ago|reply
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.
[+] [-] BrainInAJar|10 years ago|reply
[+] [-] danghica|10 years ago|reply
[+] [-] davidgerard|10 years ago|reply
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.
[+] [-] nutate|10 years ago|reply
https://github.com/ainfosec/crema
[+] [-] moyix|10 years ago|reply
http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
Edit: Oops, I see this is already linked in the main article as “accidentally Turing-complete”.
[+] [-] bbrazil|10 years ago|reply
Who doesn't want a Turing Complete monitoring language?
[+] [-] kzrdude|10 years ago|reply
Ref: https://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_ru...
[+] [-] kibwen|10 years ago|reply
[+] [-] mholt|10 years ago|reply
> 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|10 years ago|reply
[+] [-] chromaton|10 years ago|reply
[+] [-] umanwizard|10 years ago|reply
[+] [-] amyjess|10 years ago|reply
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|10 years ago|reply
[+] [-] Drup|10 years ago|reply
[+] [-] simoncion|10 years ago|reply
[+] [-] nutate|10 years ago|reply
[deleted]
[+] [-] tempodox|10 years ago|reply