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

  • How not to get people to use a new feature

    What I want to do: use my laptop. What I actually end up doing: go digging through the settings to find out why I have a new "Meet Now" icon in the…

  • Of carpentry and networking

    So, I'm not sure if I've bought a wifi router or a Cylon Raider here... Work colleague: Cylon raider. So say we all. Housegroup friend: Or a…

  • Foam filter 1, case fan 0

    Did you know that a foam dust filter is capable of milling away the leading edges of a PC case fan? That particular fan was mounted to the top…

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