3 ms·
I know this proof but I'm not happy with it. It goes out of its way to setup a Turing machine (though not a very obvious one) using M:tG cards- however, that do
by YeGoblynQueenne 8y ago
I know this proof but I'm not happy with it. It goes out of its way to setup a
Turing machine (though not a very obvious one) using M:tG cards- however, that
doesn't prove that the M:tG _game_ is Turing-complete. It proves that the
specific cards chosen can be used to create a Turing machine under a subset of
the game's rules, which is not quite the same thing.
For a more complete proof one needs to take into account the fact that the
text printed on existing cards is a derivation from some grammar - the grammar
of the M:tG "ability text" (there is no official name for the game's
language). In other words, the ability text on existing cards is no the whole
ability text language. The complete language is a superset of the strings on
existing cards. To prove the game as Turing complete, one needs to prove this
language is Turing complete- not a subset of its strings.
To give an analogy, think of the game's rules as the JVM, the ability text
grammar as the syntax of the Java language and the actually printed cards as
some arbitrarily chosen set of Java programs. You can perhaps put together a
Turing machine by stitching together those Java programs, but that will not
tell you anything about the Turing completeness of the language itself.
Instead, the straightforward proof is to use the Java syntax to write a Turing
machine and run it on the JVM.
There is, of course a slight problem with taking this approach for M:tG; that
the game's rules are very well defined (there's the Comprehensive Rules that
go a long way towards resolving any ambiguity) but there is no full
specification for the ability text language itself. So the M:tG machine is not
well defined.
Then again, it's easy to derive at least a subset of the rules of ability
text. For instance, if you see a card that says "Destroy target Elf creature",
and you know that "Elf" is a "creature" type, you can substitute "Elf" for any
creature type and generate any number of very probably correct ability text
sentences- "Destroy target Goblin creature", "Destroy target Cat creature",
"Destroy target Pirate creature" etc [1].
In this way it may be possible to generate the appropriate ability text
expressions to construct a Turing machine- and prove that the M:tG game is
Turing-complete.
________________
[1] Actually the ability to generate arbitrarily many well-formed expressions
in a language is a hallmark of Turing-completeness. If we can't assume that
the ability text on existing, printed cards is not the whole language, then
Turing completeness becomes much harder to argue for.
- myrmi 8y ago> The complete language is a superset of the strings on existing cards. To prove the game as Turing complete, one needs to prove this language is Turing complete- not a subset of its strings. It is not clear to me how a subset of a language could be Turing complete but not the whole language. Can you elaborate?
- YeGoblynQueenne 8y agoBad turn of phrase. Indeed, a Turing machine programmed in Java is a Turing machine consisting of a subset of strings in the Java language. So you are correct to doubt my claim. I'm sorry to not have a better turn of phrase. I'll keep working on it. At this point I think the best I can do is to insist on my analogy of constructing a Turing machine out of programs written in Java, rather than writing a new program implementing a Turing machine.
- rcxdude 8y agoFor most MtG players, the game rules are the sum of the game rules and the set of cards which are legal to play. Including other potential card text is not relevant, or at least at that point you are playing an unofficial variant of the game. Also, I think constructing a turing machine just under the comprehensive rules with only ability text is a very simple exercise (even exluding trivial cases like an ability text which simply instructs you to evaluate a turing machine as part of the execution). You could probably print a set of cards to make a usable assembly language, no need for any turing tarpits, which is another reason why no-one is particularly interested in this interpretation of the question.
- deleted 8y ago[deleted]
- YeGoblynQueenne 8y ago>> For most MtG players, the game rules are the sum of the game rules and the set of cards which are legal to play. Including other potential card text is not relevant, or at least at that point you are playing an unofficial variant of the game. I dont' think there is any other language for which we assume that the only strings that belong to it are the sum of its printed texts (which in the case of M:tG ability text are printed cards). I don't see why we should make this assumption for ability text. That's not how languages work, in general. Note that all this has nothing to do with "official" status, or the acceptance of specific strings by players of the game, or anyone. Either ability text is some unique construct, the likes of which has never been seen before, or it's a language like any other and it can be analysed in the same way as any other language.