4 ms·

Any discussion of Magic: the Gathering on Hacker News should come with an ObLink to how it's Turing complete https://www.toothycat.net/~hologram/Turing/HowItWo

Any discussion of Magic: the Gathering on Hacker News should come with an ObLink to how it's Turing complete https://www.toothycat.net/~hologram/Turing/HowItWorks.html https://www.toothycat.net/~hologram/Turing/HowItWorks.html For more accidentally Turing complete systems, see http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html http://beza1e1.tuxen.de/articles/accidentally_turing_complet...

deleted 8y ago
[deleted]
kingbirdy 8y ago
You should remove the angle brackets from your links, they're being included in the link and leading to 404s
deleted 8y ago
[deleted]
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 ago
    Bad 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 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. 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.

deleted 8y ago

[deleted]

kingbirdy 8y ago

You should remove the angle brackets from your links, they're being included in the link and leading to 404s

deleted 8y ago

[deleted]

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 ago
  Bad 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 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. 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.