Magic: The Gathering Is Turing Complete (2012)
toothycat.net
toothycat.net
You miss this point.
Once, as an undergrad, I had just learned about the O(n) selection algorithm (you can get the kth largest element in an unsorted list in linear time for any value of k, which is awesome)[0], and mentioned it to a grad student friend, but said "It's O(n), but the constant in the front is enormous, so it's usually totally impractical". The reply has stuck with me ever since: "I doesn't matter if this particular algorithm has a big constant. What matters is that this algorithm proves it is even possible to accomplish this task in linear time. It might not have been."
Similarly, this Magic: The Gathering Turing Complete proof is contrived, silly, impractical, and you are welcome to scoff at it all you want. The point wasn't to make something practical, it was to prove it can be done. Now all that's left is finding a practical way to do it too.
Mainly related to jealousy in my experience, with people trying to detour you with a myriad of concerns
Me: "It's O(n), but the constant in the front is enormous, so it's usually totally impractical"
?
I find it harder to say something about the median, but I imagine some similar theorems hold.
Unless you have some definition of quality for which you can show that you do need more samples with a bigger collection?
Suppose I have a set of all integers less than k and > 0, and you after N random selections want to estimate k. Presumably as k increases your accuracy drops in absolute terms. But, if you do the same thing using the reals so there is infinite number of numbers from zero to k you can still make a bounds for k.
Granted there are now infinite number of reals in your estate, but you can still pick an N such that an arbitrary % of the time k is +/- an arbitrary % of your guesses.
Quickselect is trivial to write and has a much better constant on average, but can be O(n^2).
If you do rounds of quickselect then occasionally a round of median of medians, you get guaranteed O(n) performance that on average is as close as you want to what quickselect does.
For example do quickselect on 9/10 rounds but on every 10th round do a median of medians. The overhead of guaranteed performance will only be a few percent off of the average.
It's a hybrid of quickselect and median of medians, but the switching strategy's a bit more complicated.
But basically both quickselect and median of medians are divide and conquer. Median of medians is an expensive way to guarantee a good division. Quickselect hopes for one.
If quickselect goes well, then median of medians will be relatively cheap when run because it is run on a much shorter list. If quickselect does not go well, the median of medians passes guarantee progress. So average behavior is only slightly worse, and worst case behavior is still nicely bounded (albeit with a much worse constant).
I'm not saying that it's impossible to do it and always will be. Re-read what I've said if you like, and you'll see I am simply sharing an anecdote for the purposes of an analogy about this particular situation.
To claim a system is Turing complete, what you need is (a) a store, from and to which you can read and write; (b) branching (if-statements); and (c) the ability to repeat instructions an arbitrary number of times (while-statements).
It's easy to show that M:tG has all of the above: the Stack is a store; you read from and write to it when you place abilities on and resolve them from it. Branching and loops are present in ability text sentences like the following:
You win the game if you control a land of each basic land type and a creature of each color. [1]
When you cast this spell, copy it for each spell cast before it this turn. [2]
As to a demonstration that the system actually works- you can point to any M:tG game.
Finally- the proof in the OP may not be general enough. It uses only a limited sub-set of M:tG cards, so the best we can tell is that that specific sub-set of M:tG cards is Turing complete. For a more general proof, you at least have to explain why a specific subset is chosen and explain why you can substitute it with any other subset without loss of generality.
The problem is that "card" is not a granular enough unit of the M:tG game to define as a symbol of an alphabet. A really general proof would make use of tokens of the ability text language. Such a proof would hold for any set of cards.
___________
[1] Coalition Victory: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
[2] Storm keyword ability; e.g. Dragonstorm: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
Same goes for if-statements. The statements need to be general enough and work with the rest of the system to be usable to express the Turing machine. In particular your example of an if statement that starts "you win the game if..." makes this statement sorta useless, as it ends the computation. You can't make a Turing machine if every "if" ends the program. Same goes for any other "if" in the rules - they are usually pretty limited.
"As to a demonstration that the system actually works- you can point to any M:tG game."
Again, that alone is not sufficient. It only proves that the system works for expressing one kind of computation, namely MtG games. For Turing completeness, you need to demonstrate that any Turing machine computation can be expressed as an MtG game, which is what the linked proof does.
The if-statement I quoted is just one example. The following does not end the game:
At the beginning of your upkeep, draw a card if you control the creature with the greatest toughness or tied for the greatest toughness. [1]
The important thing to note of course is that the above are well-formed sentences in the ability text language. So the language allows if-statements and it doesn't matter how many cards with if-statements are actually printed.
Also, strictly speaking, winning the game doesn't necessarily terminate processing. The ability of the card Shahrazad [2], for instance, creates a sub-game that may end without ending the original game:
Players play a MAGIC subgame, using their libraries as their decks. Each player who doesn't win the subgame loses half his or her life, rounded up.
Like I say, if you can show that the system has the components it needs to be Turing complete, then you've shown that it is Turing complete. Simulating a Turing machine is just another way to show Turing-completeness.
_______________
[1] Abzan Beastmaster, http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
[2] http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
I think you might be confused by the term "language". In the context of the proof, "language" means "anything that is the Oracle text of a card". You seem to be using it as "anything that could be printed on a card". I think you're saying "the game of Magic-but-where-I'm-allowed-to-choose-what-the-cards-say is Turing complete", which is undeniably true but also not the point.
The proof the author has given is equivalent to building a Turing machine out of existing programs in his language of interest. M:tG cards have instructions printed on them in the ability text language - so those instructions, rather than the cards themselves are the symobls in the language. The cards are best seen as scripts or small programs written in that language.
But why should anyone restrict themselves to existing cards when trying to prove the Turing completeness of the language?
Note, also, that the rules of well-formed sentences in the ability text language are given in the M:tG Comprehensive Rules or at least some of them are- there's no complete formal definition of the language. Still, there's plenty enough for anyone to be able to form syntactically correct ability text.
So, again- if you're trying to prove the Turing completeness of a language, why would you not use the full expressive power of the language to compose new strings? And instead restrict yourself to just a few pre-existing strings of it?
BTW, the kind of language the ability text language is, has a name: it's a Controlled Natural Language. [https://en.m.wikipedia.org/wiki/Controlled_natural_language].
As to the relation between the language and the rules, if you think about it, if the language is not equivalent to the rules, then it can't represent (and, therefore, modify) every rule in the game (as it is supposed to). And if the language and the rules are equivalent, then proving one is Turing complete also proves it for the other. So you can ignore the rules and focus any proof on the language.
Given such a definition of the ability text language, you don't need to restrict yourself to only those strings that are actually printed on cards.
In the same sense, we don't define the English language as every text ever written in English - but as some unknown formal system that can produce an unknown, probably infinite, number of strings that includes all text ever written in English.
So why treat the M:tg language any different?
Regarding "unnecessary", unlike typical competitive or recreational games in which players often do what they want, this particular setup results in an automaton in which players cannot disrupt the operation of the Turing machine:
"The idea of my Magic Turing machine is that the players do nothing at all, except when the game offers them a choice."
The article explains that the setup only allows choices to do optional actions, and it is assumed the players always do them. As "programming" human players to simulate a Turing machine would be too easy, they are replaced by mindless placeholders.
If you used humans, they could follow the rules in their head (with written reference sheets); tapes could be lines of objects belonging to an alphabet of different types (e.g. coins of different countries and denominations, Barbie dolls of different model years, wax crayons of different colours), and the machine head would move by walking in front of the next tape position. No need to involve a proper formal system like a card game.
Yes, I read that bit - I didn't realise it was meant to make things "harder". That alone is good enough to convince me the proof is unnecessary. If you can make a proof easier, then you make it easier. There's no need for harder proofs.
Also, the fact that the proof does not involve human actions is another piece of evidence against the generality of the proof. You can model human choices as a distribution and allow for a fully-automated proof, that doesn't require human input in the strict sense. But leaving human actions out of the proof makes it less general- because the full game does involve such actions.
(MTGox was a trading site for virtual trading cards, not real ones. It was "MTG Online: Exchange", not "MTG: Online Exchange"...)
>The model of the tape is as follows. A series of Zombie tokens controlled by Alex represent the tape to the right of the current head
However, it seems that there is a limit to the number of creature tokens in MTGO which does not exist in the paper game.
You're only allowed to say MTGO is not Turing complete if you also agree that Java is not Turing complete (because the 32-bit JVM has bounded memory it can access).
https://www.youtube.com/watch?v=AGXG5rNe_tI
For those who are confused, the card involved there is Oblivion Ring:
http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
Its effect is that, when it comes into play, you choose a non-land card in play that gets exiled (removed from play) for as long as Oblivion Ring stays in play, then gets returned once Oblivion Ring leaves play. This game devolves into a situation where there are three Oblivion Rings and no other non-land cards, so: Ring 1 exiles Ring 2, which returns Ring 3, which exiles Ring 1, which returns Ring 2, which exiles Ring 3, which returns Ring 1, which exiles Ring 2, and so on to infinity. The rules state that when a loop like this occurs (which is not often in real play), the game is an automatic draw.
[Edit] Thanks a lot to everyone who answered!
They're also quite provocative. Once every few years I'll break out my very, very old "power nine" deck and play with it at the local game store. All games stop. Everyone comes to look. People take pictures.
The cards were not that expensive when I bought them in 1994/1995 ...
Where's a good place to sell these? Ebay?
But yes, there is a lot of speculation on Magic cards. And older cards are now VERY expensive.
I couple of years ago, i found some old random magic cards from like revised with some dual lands and tossed it because I thought that they were still worth like $10 a piece.. turns out I threw away like $1500 worth of cards :(
My original collection was stolen in 1995 and would be worth as much as McMansion today. At the time it was worth about $5000.
I sold it to my cousin for $75, which was cheap because I was doing him a favor, and he never paid me.
Also consider that if you did want to sell, selling to a store drastically cuts value. Individual sales aren't without their share of problems either.
I'm heavily involved in MTG, so if you did have further questions feel free to reach out.
You can have as many tokens as you can create. The MTM (Magic Turing Machine) seems to rely on this.
It's actually within the rules to "go infinite" with tokens. For example, you have a Foo which taps (is spent) to create a Bar token. The Bar token can untap (reset) Foo. Since you can do this as much as possible, within the rules you effectively just simulate that you can repeat the combo, pick a number (100, 1 million or 1 Googolplex), and you have that many.
The proof is much more complex than that, using various creature types (zombie, rats, etc.) and other game states, but that is how the infinite memory problem can be overcome.
It's also worth noting that the infinite memory requirements is often ignored when showing Turing Completeness.
(I play a lot of Magic and just took a glance at the page)
+1/+1 counters on Zombies represent the tape to the right. +1/+1 counters on Yetis represent the tape to the left.
Whenever you reach the "end of Tape" (ie: All your Zombies are now Yetis), there's a trigger that creates a new Zombie token. Effectively creating "infinite tape". I didn't read to see how it worked on the "Yeti side", but I presume its the same concept.
Moving the tape back and forth is about putting -1/-1 counters on Yetis and +1/+1 counters on Zombies, or vice versa. Death triggers convert Yetis into Zombies and vice versa.
There are 18-states representing the "tape head" (which I presume to be the current creature with zero counters on it). I haven't really looked into how it works, but "Halt" state is pretty amusing actually. The "Halt" state kills all players, which "Halts" the program.
Another thing is, most algorithms people deal with are O(1) since people are interested in ints which can represent -2^63 to 2^63-1. But this is just an abuse of terminology, an algorithm that tries all 2^64 combinations would be a very impractical O(1) algorithm. So, we instead use a different model, and pretend integers are arbitrarily long and their length is O(logn) bits. This is now a better model for physical computers.
We went into town, to a tournament at a comic shop, and saw the games taking 20 minutes. Ours took 1-2 days.
We tried what was, to us, the “new rules” and we were disappointed, gave up. It was a big blow. Suddenly the cards were less enchanted, the decks were less sacred. Maybe if I had understood the Turing completeness of Magic, I would have had it in me to start a tournament under our rules. Well, I still could if I had written them down. I’m pretty sure they were the best rules.
to be fair to wotc, learning and playing the game nowadays is pretty straightforward.
...What were you doing?
Sorry to be an ass but I can't even guess how many "X is Turing Complete" things I've seen over the years. Turing's point wasn't to define what can be a computer, it was to define the limits of computation itself. Which is a far more interesting topic, hence my irritation with this post.
Welcome to the definition of a Turing Complete system.
Also the game in question is not "innocuous." The author admits to creating an artificial scenario under which a Turing Machine is possible.
I.e., the game design was _intended_ to be entirely decidable. Indeed, certain game rules discuss what happens when events trigger each other in a loop - and if the loop is non-halting, the game ends in a draw. This rule is only meaningful if the halting problem for M:tG is decidable!
However, in creating enough "relatively simple" cards, most of which are of the form "when one thing happens, another thing then happens", the designers of M:tG have managed to _accidentally_ create a non-decidable system.
Sure, this particular example is contrived, but it has the implications that a non-contrived game state could find itself in an undecidable state! It is theoretically possible that a natural, tournament-level game could reach a state where it can't be decided if one player or the other wins, or if it's a draw. (Or, at minimum, deciding the outcome of the game might require sufficiently convincing a tournament official of your mathematical proof that the game in fact will halt , within some known finite time).
http://www.mtgsalvation.com/forums/the-game/legacy-type-1-5/...
For that reason, it is now banned in all tournament formats. In fact, it is the only "normal" card to receive this treatment.
Yes, but only if you are:
>using them as your notation
From the linked article:
>The machine below just extends this idea
The author admits he has constructed an artificial scenario under which a Turing Machine is generated. This is exactly the same as using the rules of MtG as a notation to create a machine.
A generalized set of the rules for the game Go is Turing Complete. A generalized set of the rules for the game Go Fish is Turing Complete.
Mtg can be shown to be Turing Complete in one (of quite a few, actually) subset of rules. That's cool, and unexpected to many, and worth reading about.
And that's true for any other example of things not usually associated with programming.
(Turing completeness is an algorithmic property, not a "thing" property, so a pencil and some paper, or a bunch rocks, are certainly not Turing complete: you need procedural rules as well, something Mtg has no shortage of)
>so all you've said is
Actually what I said was "a generalized set of the rules" for Go is Turing Complete. Go in itself is not, because the end-state of the game is indeterminate. Just as a "regular-ass" game of MtG without a very specific and artificial construction is not Turing Complete, in and of itself.
>That's cool
I can appreciate stamp collecting, and I don't want to say that it's an invalid use of time. There are plenty of worse hobbies. But my point is that any of an infinite, arbitrary, and inconsequential number of conceivable systems are "Turing Complete," and personally I don't find this very compelling.
How many books in the Library of Babel[1] describe a Turing Complete system?
>Turing completeness is/is not
I stated as much in a comment below, or you could have inferred the same by my interpretation of the XKCD comic, but thanks for assuming I'm incompetent and acting in bad faith.
I think most people assumed that Turing-Completeness requires a specific and artificial construction, which is where the disconnected (and downvotes) are coming from. Especially for something wasn't previously believed to be a model of computation at all, much less a Turing-Complete one.
An artificial scenario which is achievable under normal play, and the only variation required by the human players being that when offered a choice, they choose affirmative.
> A generalized set of the rules for the game Go is Turing Complete. A generalized set of the rules for the game Go Fish is Turing Complete.
Do you have references for those? I would be interested in seeing how they simulated the tape.
With some contrieved meaning of the cards, which has nothing to do with the "meaning of the card" in Magic the game, like "State B, Colour 16: Stay in state B, colour this space 18, move one step right." it recreates a complicated and arcane turing machine.
'Reanimator 17B actually says "Whenever a Rat (R0) dies, make a Sliver (S1M).'
The linked page is not using the rules of Magic the gathering or the texts on the cards, but uses it's own rules what cards mean.
The game rules of magic the gathering are not turing complete, because the linked post is not talking about Magic the Gathering game.
What's interesting is actual MTG gameplay uses a HUGE amount of shortcuts on every play, because saying every single thing you and the opponent have to do during each step and phase would be incredibly time consuming.
If you play Commander or multiplayer, then its usually a heck of a lot less formal. Ive also played some local tournament games where the players were good-natured and we all just had fun.
Then I've played some tournaments locally and at Gencon that were methodical and clockwork style "Please indicate what you did, step by ste-COUNTER". Or you get the priority police up and running, where you have to explicitly pass priority. I hate those games with a passion - it just drains the fun out via rules-lawyering.
I've not played in a few years, primarily because the game was feeling much more like 'loot crates' that I've railed against prior. And with $3.50/pack, I didn't feel like I was getting enjoyment. You either buy buy buy, or get left in the dust and destroyed in games because you didnt buy buy buy.
What's the advantage over simply specifying the moment you wanted to react out of the last batch of actions (like a normal person)? If the opponent skips too many steps and gives up some critical information as a result -- his problem.
And that next game, they'll say "ditch that deck or you aren't playing".
These days, I play explicit decks that have a neat theme and good win conditions (I have 2 decks left). They dont use infinite combos (they win, but are unfun), and I play to have a good time. If I lose, it was because I had some good threats and a blast of a game.
Transmission, storage with magnetic interactions of electrical actions, small size of components, speed of transmission -- aren't these properties that make for more practical Turing machines?
Parked cars are going to take ages to do anything useful with, no.
(IANAComputerScientist)
No one disputes that a modern computer implementing a Turing machine is going to calculate faster than manually manipulating MTG cards.
However, better here means 'more expressive'. Turing completeness is concerned with whether or not a computational system is 'universal' or not. In other words, whether that computational system can compute everything that another computational system could. If two systems can both be shown to simulate a Turing machine, then that means that those systems could compute the same exact set of things (given enough time).
So with regards to expressiveness (or the things a system could theoretically compute), since a modern computer can implement a Turing machine and a MTG game can implement a Turing machine, they are both the same, and thus neither is 'better'. In other words, the addition of electricity doesn't effect what a system could theoretically compute.
It is precisely this ability to map seemingly arbitrary and meaningless physical manifestations of turning machines to the abstract that provides the concept so much power. By being able to provably map the implementation to the concept you're able to get all the "benefits" of the concept without having to individually prove them in your implementation where it might be really difficult or just time consuming to prove everything individually.
This, coincidentally, is the same reason mathematics is so obsessed with isomorphisms, homeomorphisms, homomorphisms etc. They are all different ways of saying "this thing stays the same, even when it changes" which many times means that things proven in a place where it's easy to prove are maintained in places where it's very difficult or even impossible to prove (absent the isomorphism).
Thanks, didn't know "colour this space 18" was a concept in MTG now, I haven't played for 2 decades I assume (stopped before Legends, no clue what came afterwards).
I can forgive the extremely contrived decks, but using a card to completely change the behavior of the majority of your cards doesn't mean the game itself is Turing complete. If anything, this is just showing how you can utilize Magic game mechanics to create a Turing Machine.
Aren't those two statements equivalent?
I believe that is the point.