Thomas (boggyb) wrote,

  • Mood:
  • Music:

Turing completeness

Hmm, I've just realised that talismancer hasn't yet posted today (the last couple of days he's posted shortly after midnight).

Anyway, a post! Hmm... let's expand a bit on yesterday's post (which was actually a coherent post - but then again, talismancer is one of the people I'd expect to have understood it).

The Turing machine is a hypothetical computer that (in the form originally described by Alan Turing) consists of an infinite paper tape, a read/write head that can step along the tape, a set of rules for processing the current symbol on the tape, and some concept of which state the machine is in. Generally the machine will read the current symbol, consult the rules table to work out what to do, and then do some combination of changing internal state, writing a new symbol, and step the tape head one position. Since a true implementation requires an infinite paper tape there's no such thing as an actual Turing machine, but a practical system with a finite tape (real or virtual) is usually good enough.

The real usefulness of a Turing machine is that it can emulate any computer, by first being fed a tape with suitable instructions. This also means that if you can implement a Turing machine in a given system, then that system is capable of emulating any other computer system. Programming languages that can do this are described as being "Turing complete".

Most general-purpose programming languages (like Basic, C, and Python) are usually Turing complete, because it turns out that the functionality needed to make them useful is more-or-less the same as that required for a Turing machine. Some more unusual languages that you wouldn't normally consider to be programming languages (including formatting languages like PostScript and XSLT) are also Turing complete. Interestingly standard SQL (a query language) isn't Turing complete, though some variants are.

So in yesterday's post when I said that the Magic the Gathering card game is Turing complete, what this means is that MtG can actually be used as a computer. A totally impractical computer, but a computer nonetheless (note that this is a more traditional definition of a computer being something that calculates a solution to a problem, not a thing which you play Minesweeper on - although it can do that too, if you come up with a way to provide input and output).

One result of this is that it is theoretically possible to use MtG to simulate a MtG game. Another fun result is that the Halting problem applies to MtG, and so it is provably impossible to determine in general if a game of MtG will ever end (note that you can determine if some games will end, but not if all games will).
Tags: computing, nablopomo

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.