7 ms·

Accidentally Turing-Complete

108 points by ggreer 13y ago

fiatmoney 13y ago
I'd add to that list XSLT: http://www.unidex.com/turing/utm.htm http://www.unidex.com/turing/utm.htm
- saurik 13y ago
  XSLT is somewhat explicitly a programming environment: that's how people use it, and the extent to which the syntax for it was awkward in XSLT 1 it was all made almost reasonable in XSLT 2. Like, even in XSLT 1, the only mental gymnastic you have to do is say "function" every time you see "template": the language already has "parameters" and a "call" primitive, so it is a straightforward functional language. What makes this list interesting is that these things have to be twisted in weird ways to become programming environments. Putting XSLT on the list is more like putting brainfuck on the list: its irritating the program in, but it isn't surprising that it's turing complete.
gwern 13y ago
I list a few others in http://www.gwern.net/Notes#surprising-turing-complete-languages http://www.gwern.net/Notes#surprising-turing-complete-langua...
KimberlyJClark 13y ago
my classmate's mother-in-law makes $67 an hour on the computer. She has been fired for 7 months but last month her pay check was $18297 just working on the computer for a few hours. this page ========================== http://WWW.Works23.Com http://WWW.Works23.Com
Rampoina 13y ago
I did not expect Magic: The Gathering
- gweinberg 13y ago
  Well, it must depend on what cards are available. If it's turing complete, you must be able to get infinite loops. You won't be able to do that just by playing land and summoning monsters, but if you have cards that say something like "put your graveyard at the bottom of yor library", you could get an infinite loop. If there is some horrible card that says something like "take any valid card that you own and shuffle it into your library" you have something that goes beyond turing complete and into oracle territory.
  - thaumasiotes 13y ago
    http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=34402 http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
    - lifeformed 13y ago
      Technically, "from outside of the game" just refers to your sideboard, and cards that have been removed from the game. But in a casual setting it's usually used for anything.
      - thaumasiotes 13y ago
        The official stance is that in sanctioned tournaments you only own the cards in your registered decklist (or put another way, only the cards in your registered decklist exist). And outside of sanctioned tournaments, you own all the cards you own.
        Dylan16807 13y ago
        The official stance screwed up those cards anyway. The card clearly states to remove death wish from the game. Logically you should be able to use another wish to get it back. But they retconned it to say 'exile', and 'exile' puts cards into a place that is still 'inside' the game.
  - 13y ago
StefanKarpinski 13y ago
"Mean time to turing completeness" is a mental metric that I use to decide whether making a domain-specific language is warranted or it would be better to just use a general purpose language. If you can really limit the scope of the task to something non-turing complete, then a DSL might be a good idea. If you don't think you can keep the thing from becoming turing complete, you're going to fall prey to Greenspun's Tenth Rule [1] and you might as well skip all the nonsense and just use a Lisp in the first place (or another well-designed, fully powered language). [1] http://en.wikipedia.org/wiki/Greenspun's_tenth_rule http://en.wikipedia.org/wiki/Greenspun's_tenth_rule
- eru 13y ago
  Deliberately limiting the power of your (domain specific) language can be a useful thing to do, too. As an example, SQL (ignoring the crazy bits) is so amenable to query optimization precisely because it is not Turing complete.
  - nly 13y ago
    Indeed. Bitcoin transactions all contain validation scripts that are run through a stack-based interpreter. This Forth-like language does lack loops but, even after being there for years, the current client still only accepts a small set of standard templates.
  - mtdewcmu 13y ago
    This has been codified in the Rule of Least Power: http://en.wikipedia.org/wiki/Rule_of_least_power http://en.wikipedia.org/wiki/Rule_of_least_power
  - tel 13y ago
    This shows up all the time in the myriad Haskell eDSLs. Monad-based interfaces are obvious but throw away information that is useful for optimization (see http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pdf http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pd... for how to get some of it back). Applicative interfaces are really amenable to optimization, though (see Facebook's Haxl project: http://www.reddit.com/r/haskell/comments/1le4y5/the_haxl_project_at_facebook_slides_from_my_talk/ http://www.reddit.com/r/haskell/comments/1le4y5/the_haxl_pro...)
chocolateboy 13y ago
Also: * Little Big Planet [1] * Scala's type system [2] [1] http://forums.xkcd.com/viewtopic.php?f=12&t=57034#p2029587 http://forums.xkcd.com/viewtopic.php?f=12&t=57034#p2029587 [2] http://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-ski-calculus/ http://michid.wordpress.com/2010/01/29/scala-type-level-enco...
mprovost 13y ago
Dwarf Fortress is Turing complete. http://boingboing.net/2010/04/15/colossal-turing-mach.html http://boingboing.net/2010/04/15/colossal-turing-mach.html
- ekimekim 13y ago
  I'm reasonably sure that one was intentional. Or at least, noted by the creator upon creation.
drakaal 13y ago
I don't think Turing-Complete is much of a barrier anymore. I could write a Turing Machine in QBasic, or Java, or MineCraft. Ok, I couldn't do it in minecraft cause I don't play, but I know that it is possible to do in minecraft. I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Saying something is Turing Complete is kind of like saying "Could you write a Nintendo emulator" for it. Once you get beyond a certain level of computational power and memory, you can, even if it would be very slow.
- derleth 13y ago
  > I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Depending on how you define 'Turing-equivalent' this is never a problem: Something is Turing-equivalent if and only if you always have enough memory for the current computation. Note that you do not have infinite memory, merely sufficient memory, another pedantic distinction sometimes harped upon. The above distinctions are frequently disregarded in actual conversations because they reduce a useful term to something which can only have application to the most theoretical parts of Computer Science. Finally, a third distinction: Problems are Turing-complete. Machines are Turing-equivalent. Cite: http://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co/ http://scienceblogs.com/goodmath/2007/01/05/turing-equivalen...
  - mdxn 13y ago
    Your definitions of Turing-Complete and Turing Equivalent, as phrased, are incorrect or perhaps mistaken to some extent. I don't want to Arbitrarily scalable memory is just one necessary component for Turing-equivalence to a Turing Machine. Two machines are Turing Equivalent when they can simulate each other. Not that this does not necessarily extend to general computation and can actually be a limited for of such. Countably unbounded memory is not necessarily a requirement (ex. some symbolic systems), but might as well be for the class of machines that you are thinking of. A lot of models of computation become Turing-complete when they receive this benefit. You also need to keep in mind that some automata can have infinite memory, but don't have the ability to take advantage of it. Straightforward examples include pushdown automata and time bounded machines. Machines that do not have a logically complete algebra will also have this problem. I complete agree with you about the "finite memory" objection people like to use. I find it incredibly annoying and not very productive. It is almost ignorant to discussion going on as they are completely missing the point. It's insulting that they think others don't realize this. I'm glad someone else (you) here shares this feeling. :) I believe you meant that problems can be R.E.-complete (semidecidable in a complete way; ex. Halting problem). The term, Turing Complete, is inapplicable in this situation. It describes properties of a formal system and/or model of computation (which I'm certain you knew).
spellboots 13y ago
Apache rewrite rules, which isn't that surprising if you've seen as many abominations of config as I have: http://olsner.se/2008/01/21/an-excursion-in-mod_rewrite/ http://olsner.se/2008/01/21/an-excursion-in-mod_rewrite/
leoc 13y ago
Many of these have entries in the 99 Bottles of Beer website http://www.99-bottles-of-beer.net/ http://www.99-bottles-of-beer.net/ . Konrad Zuse's Z3 computer belongs on the list https://en.wikipedia.org/wiki/Z3_(computer) https://en.wikipedia.org/wiki/Z3_(computer) , making it accidentally the first ever actually-constructed Turing-equivalent* computer. There may be some kind of lesson there. (Zuse evidently wasn't unaware of the possibility of Turing-complete computation though: he designed the first high-level programming language https://en.wikipedia.org/wiki/Plankalk%C3%BCl https://en.wikipedia.org/wiki/Plankalk%C3%BCl before the end of the war.) * (Or memory-limited finite approximation to a Turing-equivalent computer, like any other actual computer, of course.)
mdxn 13y ago
I would advise that everyone take more care when assessing the Turing Completeness various models of computation. Many analyses that I have seen do a check for logical completeness, but forget to rigorously check that you have scalable and fully accessible memory, even in the most generalized cases. Even if you assume that some resource is unbounded, your other mechanics might not actually allow you to interface with it, even if they do work on a constant/small scale (locality of computation does not necessarily imply this). You could take a turing machine its infinite tape, but forget to show that you can move it left or right an arbitrary number of times. On the flip side, another ridiculous assumption involves including the power of human operation. Yes, an abacus is "Turing Complete" if it is infinitely large and you, as a human being, do the logic in your head. Pen and paper is Turing Complete by the same reasoning (this is ridiculous). Yes, we know that humans are capable of computation. I might grant that you have scalable memory in these situations, but where's the automation of your logic? Here's an example of the first: I suspect that the in-game mechanics of a generalized version of Minecraft to not be Turing Complete. By generalized, I mean that you remove the chunk loading and update limitations, giving you a countably large playing field. I, of course, am not considering limitations (or benefits) of Java, the machine running it, or unintended behavior (bizarre bugs). Forgo things like command blocks and bizarre uses of spawn eggs/entities, just consider legitimately obtainable resources (we can assess TC with these later). To briefly sketch the idea, when you have a constant sized machine (accessing arbitrarily sized input), the selected mechanics are too limited by construction to "grow" the equivalent to a Turing Machine's work tape. A superficial reason for this is because the mechanics are coded to only extend locally (note that this is distinct from the "computation is local" result). For example, using pistons to push only goes out 11 blocks before it fails. You can chain multiple of these together, but only a constant number. You also need controllable Redstone signal to extend far enough to change their states. With a bit more work, you can show that mechanical self propulsion using pistons is not possible (there's a giant thread on Minecraft Forums concerning this), even in one direction. Three simple reasons for this: 1. You cannot push extended pistons, 2. you cannot push/pull/power your back most piston without "leaking" blocks, and 3. you cannot make a pushable clock. Your ability to shift around and access your tape/memory or move your Turing "head"/logic in this approach goes out the window. For block based memory (to make use of infinite "block space") in general, you not only have to move a number of blocks of an arbitrary number to locations an arbitrary distance away, but you have to autonomously generate and destroy an arbitrary number of blocks, too. Cobblestone, Ice, Pumpkins, and Melons all do this and are thankfully Redstone distinguishable, so we at least have our endless supply of symbols for such a tape. There are additional requirements and engineering challenges, but they fall outside the purpose of this post. Issues like these are not considered in almost all the claims Minecraft's Turing Completeness that I have seen. They absolutely should be. Obviously there may be ways around this, but I hope my point is clear. Make sure the application of your "proofs" or constructions actually make sense. Make sure they demonstrate how to handle the memory and the logic (algebra) necessary. And for god's sake, make sure that your model is actually an automaton (I'm looking at you Magic and LBP). On a side note, I did start compiling a paper on the computational complexity of Minecraft a while ago, but left it unfinished. It goes through various generalizations, starting from some most basic (just blocks, redstone, etc.), adding some components like randomness, commandblocks, entities. Even some structural assumptions such as superflat worlds and tiled machines (works for Conways game of life). I lost some motivation because I did not believe people would care enough to be worth my time. Even if I were to pick it up again, the game has changed quite a bit since 1.7 came out. My results might be outdated (new commandblock functionality changes things greatly). However, if others show interest, I could perhaps start working on it again.
greesil 13y ago
So we're talking about c++ templates?
TheZenPsycho 13y ago
Server Side Includes are turing complete http://www.janschejbal.de/projekte/ssituring/ http://www.janschejbal.de/projekte/ssituring/
rheide 13y ago
Another example of this that I love is that you can build logic gates in Transport Tycoon (well, OpenTTD) using trains and rail signals: http://www.tt-forums.net/viewtopic.php?f=29&t=37902 http://www.tt-forums.net/viewtopic.php?f=29&t=37902.
michh 13y ago
The notoriously complex config syntax of sendmail has also been proven to be Turing complete: http://okmij.org/ftp/Computation/sendmail-as-turing-machine.txt http://okmij.org/ftp/Computation/sendmail-as-turing-machine....

108 points by ggreer 13y ago

fiatmoney 13y ago

I'd add to that list XSLT: http://www.unidex.com/turing/utm.htm http://www.unidex.com/turing/utm.htm

saurik 13y ago
XSLT is somewhat explicitly a programming environment: that's how people use it, and the extent to which the syntax for it was awkward in XSLT 1 it was all made almost reasonable in XSLT 2. Like, even in XSLT 1, the only mental gymnastic you have to do is say "function" every time you see "template": the language already has "parameters" and a "call" primitive, so it is a straightforward functional language. What makes this list interesting is that these things have to be twisted in weird ways to become programming environments. Putting XSLT on the list is more like putting brainfuck on the list: its irritating the program in, but it isn't surprising that it's turing complete.

gwern 13y ago

I list a few others in http://www.gwern.net/Notes#surprising-turing-complete-languages http://www.gwern.net/Notes#surprising-turing-complete-langua...

KimberlyJClark 13y ago

my classmate's mother-in-law makes $67 an hour on the computer. She has been fired for 7 months but last month her pay check was $18297 just working on the computer for a few hours. this page ========================== http://WWW.Works23.Com http://WWW.Works23.Com

Rampoina 13y ago

I did not expect Magic: The Gathering

gweinberg 13y ago
Well, it must depend on what cards are available. If it's turing complete, you must be able to get infinite loops. You won't be able to do that just by playing land and summoning monsters, but if you have cards that say something like "put your graveyard at the bottom of yor library", you could get an infinite loop. If there is some horrible card that says something like "take any valid card that you own and shuffle it into your library" you have something that goes beyond turing complete and into oracle territory.
- thaumasiotes 13y ago
  http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=34402 http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
  - lifeformed 13y ago
    Technically, "from outside of the game" just refers to your sideboard, and cards that have been removed from the game. But in a casual setting it's usually used for anything.
    - thaumasiotes 13y ago
      The official stance is that in sanctioned tournaments you only own the cards in your registered decklist (or put another way, only the cards in your registered decklist exist). And outside of sanctioned tournaments, you own all the cards you own.
      - Dylan16807 13y ago
        The official stance screwed up those cards anyway. The card clearly states to remove death wish from the game. Logically you should be able to use another wish to get it back. But they retconned it to say 'exile', and 'exile' puts cards into a place that is still 'inside' the game.
- 13y ago

StefanKarpinski 13y ago

"Mean time to turing completeness" is a mental metric that I use to decide whether making a domain-specific language is warranted or it would be better to just use a general purpose language. If you can really limit the scope of the task to something non-turing complete, then a DSL might be a good idea. If you don't think you can keep the thing from becoming turing complete, you're going to fall prey to Greenspun's Tenth Rule [1] and you might as well skip all the nonsense and just use a Lisp in the first place (or another well-designed, fully powered language). [1] http://en.wikipedia.org/wiki/Greenspun's_tenth_rule http://en.wikipedia.org/wiki/Greenspun's_tenth_rule

eru 13y ago
Deliberately limiting the power of your (domain specific) language can be a useful thing to do, too. As an example, SQL (ignoring the crazy bits) is so amenable to query optimization precisely because it is not Turing complete.
- nly 13y ago
  Indeed. Bitcoin transactions all contain validation scripts that are run through a stack-based interpreter. This Forth-like language does lack loops but, even after being there for years, the current client still only accepts a small set of standard templates.
- mtdewcmu 13y ago
  This has been codified in the Rule of Least Power: http://en.wikipedia.org/wiki/Rule_of_least_power http://en.wikipedia.org/wiki/Rule_of_least_power
- tel 13y ago
  This shows up all the time in the myriad Haskell eDSLs. Monad-based interfaces are obvious but throw away information that is useful for optimization (see http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pdf http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pd... for how to get some of it back). Applicative interfaces are really amenable to optimization, though (see Facebook's Haxl project: http://www.reddit.com/r/haskell/comments/1le4y5/the_haxl_project_at_facebook_slides_from_my_talk/ http://www.reddit.com/r/haskell/comments/1le4y5/the_haxl_pro...)

chocolateboy 13y ago

Also: * Little Big Planet [1] * Scala's type system [2] [1] http://forums.xkcd.com/viewtopic.php?f=12&t=57034#p2029587 http://forums.xkcd.com/viewtopic.php?f=12&t=57034#p2029587 [2] http://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-ski-calculus/ http://michid.wordpress.com/2010/01/29/scala-type-level-enco...

mprovost 13y ago

Dwarf Fortress is Turing complete. http://boingboing.net/2010/04/15/colossal-turing-mach.html http://boingboing.net/2010/04/15/colossal-turing-mach.html

ekimekim 13y ago
I'm reasonably sure that one was intentional. Or at least, noted by the creator upon creation.

drakaal 13y ago

I don't think Turing-Complete is much of a barrier anymore. I could write a Turing Machine in QBasic, or Java, or MineCraft. Ok, I couldn't do it in minecraft cause I don't play, but I know that it is possible to do in minecraft. I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Saying something is Turing Complete is kind of like saying "Could you write a Nintendo emulator" for it. Once you get beyond a certain level of computational power and memory, you can, even if it would be very slow.

derleth 13y ago
> I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Depending on how you define 'Turing-equivalent' this is never a problem: Something is Turing-equivalent if and only if you always have enough memory for the current computation. Note that you do not have infinite memory, merely sufficient memory, another pedantic distinction sometimes harped upon. The above distinctions are frequently disregarded in actual conversations because they reduce a useful term to something which can only have application to the most theoretical parts of Computer Science. Finally, a third distinction: Problems are Turing-complete. Machines are Turing-equivalent. Cite: http://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co/ http://scienceblogs.com/goodmath/2007/01/05/turing-equivalen...
- mdxn 13y ago
  Your definitions of Turing-Complete and Turing Equivalent, as phrased, are incorrect or perhaps mistaken to some extent. I don't want to Arbitrarily scalable memory is just one necessary component for Turing-equivalence to a Turing Machine. Two machines are Turing Equivalent when they can simulate each other. Not that this does not necessarily extend to general computation and can actually be a limited for of such. Countably unbounded memory is not necessarily a requirement (ex. some symbolic systems), but might as well be for the class of machines that you are thinking of. A lot of models of computation become Turing-complete when they receive this benefit. You also need to keep in mind that some automata can have infinite memory, but don't have the ability to take advantage of it. Straightforward examples include pushdown automata and time bounded machines. Machines that do not have a logically complete algebra will also have this problem. I complete agree with you about the "finite memory" objection people like to use. I find it incredibly annoying and not very productive. It is almost ignorant to discussion going on as they are completely missing the point. It's insulting that they think others don't realize this. I'm glad someone else (you) here shares this feeling. :) I believe you meant that problems can be R.E.-complete (semidecidable in a complete way; ex. Halting problem). The term, Turing Complete, is inapplicable in this situation. It describes properties of a formal system and/or model of computation (which I'm certain you knew).

spellboots 13y ago

Apache rewrite rules, which isn't that surprising if you've seen as many abominations of config as I have: http://olsner.se/2008/01/21/an-excursion-in-mod_rewrite/ http://olsner.se/2008/01/21/an-excursion-in-mod_rewrite/

leoc 13y ago

Many of these have entries in the 99 Bottles of Beer website http://www.99-bottles-of-beer.net/ http://www.99-bottles-of-beer.net/ . Konrad Zuse's Z3 computer belongs on the list https://en.wikipedia.org/wiki/Z3_(computer) https://en.wikipedia.org/wiki/Z3_(computer) , making it accidentally the first ever actually-constructed Turing-equivalent* computer. There may be some kind of lesson there. (Zuse evidently wasn't unaware of the possibility of Turing-complete computation though: he designed the first high-level programming language https://en.wikipedia.org/wiki/Plankalk%C3%BCl https://en.wikipedia.org/wiki/Plankalk%C3%BCl before the end of the war.) * (Or memory-limited finite approximation to a Turing-equivalent computer, like any other actual computer, of course.)

mdxn 13y ago

I would advise that everyone take more care when assessing the Turing Completeness various models of computation. Many analyses that I have seen do a check for logical completeness, but forget to rigorously check that you have scalable and fully accessible memory, even in the most generalized cases. Even if you assume that some resource is unbounded, your other mechanics might not actually allow you to interface with it, even if they do work on a constant/small scale (locality of computation does not necessarily imply this). You could take a turing machine its infinite tape, but forget to show that you can move it left or right an arbitrary number of times. On the flip side, another ridiculous assumption involves including the power of human operation. Yes, an abacus is "Turing Complete" if it is infinitely large and you, as a human being, do the logic in your head. Pen and paper is Turing Complete by the same reasoning (this is ridiculous). Yes, we know that humans are capable of computation. I might grant that you have scalable memory in these situations, but where's the automation of your logic? Here's an example of the first: I suspect that the in-game mechanics of a generalized version of Minecraft to not be Turing Complete. By generalized, I mean that you remove the chunk loading and update limitations, giving you a countably large playing field. I, of course, am not considering limitations (or benefits) of Java, the machine running it, or unintended behavior (bizarre bugs). Forgo things like command blocks and bizarre uses of spawn eggs/entities, just consider legitimately obtainable resources (we can assess TC with these later). To briefly sketch the idea, when you have a constant sized machine (accessing arbitrarily sized input), the selected mechanics are too limited by construction to "grow" the equivalent to a Turing Machine's work tape. A superficial reason for this is because the mechanics are coded to only extend locally (note that this is distinct from the "computation is local" result). For example, using pistons to push only goes out 11 blocks before it fails. You can chain multiple of these together, but only a constant number. You also need controllable Redstone signal to extend far enough to change their states. With a bit more work, you can show that mechanical self propulsion using pistons is not possible (there's a giant thread on Minecraft Forums concerning this), even in one direction. Three simple reasons for this: 1. You cannot push extended pistons, 2. you cannot push/pull/power your back most piston without "leaking" blocks, and 3. you cannot make a pushable clock. Your ability to shift around and access your tape/memory or move your Turing "head"/logic in this approach goes out the window. For block based memory (to make use of infinite "block space") in general, you not only have to move a number of blocks of an arbitrary number to locations an arbitrary distance away, but you have to autonomously generate and destroy an arbitrary number of blocks, too. Cobblestone, Ice, Pumpkins, and Melons all do this and are thankfully Redstone distinguishable, so we at least have our endless supply of symbols for such a tape. There are additional requirements and engineering challenges, but they fall outside the purpose of this post. Issues like these are not considered in almost all the claims Minecraft's Turing Completeness that I have seen. They absolutely should be. Obviously there may be ways around this, but I hope my point is clear. Make sure the application of your "proofs" or constructions actually make sense. Make sure they demonstrate how to handle the memory and the logic (algebra) necessary. And for god's sake, make sure that your model is actually an automaton (I'm looking at you Magic and LBP). On a side note, I did start compiling a paper on the computational complexity of Minecraft a while ago, but left it unfinished. It goes through various generalizations, starting from some most basic (just blocks, redstone, etc.), adding some components like randomness, commandblocks, entities. Even some structural assumptions such as superflat worlds and tiled machines (works for Conways game of life). I lost some motivation because I did not believe people would care enough to be worth my time. Even if I were to pick it up again, the game has changed quite a bit since 1.7 came out. My results might be outdated (new commandblock functionality changes things greatly). However, if others show interest, I could perhaps start working on it again.

greesil 13y ago

So we're talking about c++ templates?

TheZenPsycho 13y ago

Server Side Includes are turing complete http://www.janschejbal.de/projekte/ssituring/ http://www.janschejbal.de/projekte/ssituring/

rheide 13y ago

Another example of this that I love is that you can build logic gates in Transport Tycoon (well, OpenTTD) using trains and rail signals: http://www.tt-forums.net/viewtopic.php?f=29&t=37902 http://www.tt-forums.net/viewtopic.php?f=29&t=37902.

michh 13y ago

The notoriously complex config syntax of sendmail has also been proven to be Turing complete: http://okmij.org/ftp/Computation/sendmail-as-turing-machine.txt http://okmij.org/ftp/Computation/sendmail-as-turing-machine....