Accidentally Turing-Complete

http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html

by ggreer • 13 years ago

108 48 13 years ago

beza1e1.tuxen.de

fiatmoney• 13 years ago

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

saurik• 13 years 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• 13 years ago

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

Rampoina• 13 years ago

I did not expect Magic: The Gathering

gweinberg• 13 years 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.

thaumasiotes2• 13 years ago

http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

mackal• 13 years ago

It is entirely possible to generate infinite loops in MTG. You can generate inifinite mana, damage, health etc, bring back cards from the graveyard etc. If you have the right hand and cards in play these are easy to do. I remember playing at a tourney and my opponent got off a combo that did unlimited damage and mana, I was very sad.

jimminy• 13 years ago

Here's a link that explains the Turing-completeness of Magic the Gathering. http://www.toothycat.net/~hologram/Turing/index.html

StefanKarpinski• 13 years 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

eru3• 13 years 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• 13 years 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• 13 years ago

This has been codified in the Rule of Least Power: http://en.wikipedia.org/wiki/Rule_of_least_power

tel2• 13 years 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.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_pro...)

chocolateboy• 13 years ago

Also:

* Little Big Planet [1]

* Scala's type system [2]

[1] http://forums.xkcd.com/viewtopic.php?f=12&t=57034#p2029587

[2] http://michid.wordpress.com/2010/01/29/scala-type-level-enco...

mprovost• 13 years ago

Dwarf Fortress is Turing complete.

http://boingboing.net/2010/04/15/colossal-turing-mach.html

ekimekim• 13 years ago

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

drakaal• 13 years 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• 13 years 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-equivalen...

mdxn9• 13 years 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).

jlgreco• 13 years ago

I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory.

Well of course. A TI-81 is "a computer" in the layman's sense of the term. It has a general purpose Zilog z80 processor that can be programmed by the end user with a BASIC dialect, and (recently, with a exploit discovered in TI's software on it) with z80 assembly.

Pointing out that a TI-81 is Turing equivalent is like pointing out that an iPhone is Turing equivalent. It was never pretending not to be.

lifeformed2• 13 years ago

The point of this is that these things are entirely not intended to be computational systems, yet just through their complexity they ended up being Turing Complete unintentionally.

spellboots• 13 years 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/

leoc• 13 years ago

Many of these have entries in the 99 Bottles of Beer website http://www.99-bottles-of-beer.net/ .

Konrad Zuse's Z3 computer belongs on the list 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 before the end of the war.)

* (Or memory-limited finite approximation to a Turing-equivalent computer, like any other actual computer, of course.)

mdxn9• 13 years 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.

Houshalter• 13 years ago

Wouldn't that apply to a normal computer though? Nothing has infinite memory.

mdxn9• 13 years ago

When we talk about models of computation, we typically look at ones where some sort of resource is unbounded. In the case with generalized Minecraft, both time and block space are unbounded. The hope is to translate that block space resource and use it as memory. I was bringing up the point that this may be not possible since the mechanics do not allow enough access. This is interesting because a first approach to constructing scalable computer memory in Minecraft is to encode things with infinitely generable blocks. We have infinite sources of necessary components used for memory, but run into the barrier of operating things over arbitrary distances (communication). Even the case where you tile redstone based memory cells is just as difficult for the same reason. This is different than the case with a "normal computer" since there's no unbounded/scalable resource to consider.

eru3• 13 years ago

Pen and paper is Turing Complete by the same reasoning (this is ridiculous).

You know, codifying pen-and-paper computations is how Alan Turing came up with his machine in the first place.

mdxn9• 13 years ago

Can you elaborate on this? I'm not sure what your point is or how it relates to my comment.

Dylan168075• 13 years ago

Magic is just as Turing complete as a Turing machine is. Magic is an abstract system, not pieces of cardboard. Just like a Turing machine is an abstract idea rather than a physical box. You can run the logic of a magic game using circuits, or gears, or humans, but it's fundamentally based on taking a set of rules and implementing them. The reason pen and paper is different is that a pen is not a rule-based system, it's merely an object. Same for an abacus.

mdxn9• 13 years ago

I believe you have misunderstood what I have said. My issue with Magic was not with the logic specifically. It is with the fact that it requires the player to initiate state transition by specifically selecting actions. It would be permissible if the player simply functioned as a clock, but some of the state transition logic is actually shifted over to the player. It certainly is better than the pen and paper scenario, but the rule system is incomplete. It still requires a couple of rules for the player to follow (just as pen/paper or an abacus does).

The author mentions this problem explicitly on the "Difficulties" section of the site. It is very important to note this. The hope is for the effects of some cards to allow for the necessary computational depth to capture all of computation without additional human action (besides, lets say, initialization). People often look at Turing Machines and their components. They forget to think about state transitions and the recursion involved (recursion really is the "meat" of computation).

greesil• 13 years ago

So we're talking about c++ templates?

TheZenPsycho• 13 years ago

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

rheide• 13 years 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.

michh• 13 years 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....

Accidentally Turing-Complete

Related Stories