3 ms·

"The language allows if-statements and loops" is not sufficient for the language to be Turing-complete. A language with loops in which the only form of selectio

"The language allows if-statements and loops" is not sufficient for the language to be Turing-complete. A language with loops in which the only form of selection is "if 4 > 3 then…" is not Turing-complete. Just pointing to a specific if-statement appearing on a card and saying "yeah, that's probably enough to make Magic Turing-complete" does not constitute a proof. 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.

YeGoblynQueenne 9y ago
Yes, that's exactly what I'm saying- why is it not the point? If you were trying to prove that Java is Turing-complete you wouldn't look at all the Java programs ever written and try to build a Turing machine with those programs. Instead, you'd use the symbols in the language to write a (new) program that simulates a Turing machine, or a set of functions that suffice to prove Turing completeness. 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?
- rcxdude 9y ago
  The game of 'Magic: The Gathering' consists of both the rules and the cards available in it (which are written in a kind of language). If you are printing your own cards, most players would agree you are not really playing 'Magic: The Gathering', but your own homebrew game based on it.
  - YeGoblynQueenne 9y ago
    Maybe, but if we're doing formal proofs then we're not in the realm of opinion anymore. So the point is to substantiate any claim as to what, exactly, is reasonable to call "the mtg language". I really doubt there's any context in which a language can be formally described as "a limited number of texts"... especially if that language is supposed to be Turing complete (which implies non - finite-ness) ! 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 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.
  - YeGoblynQueenne 9y ago
    Just to make it plain. In formal language theory, a language is a set of symbols and a set of rules that determine what is a valid string. 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?

YeGoblynQueenne 9y ago

Yes, that's exactly what I'm saying- why is it not the point? If you were trying to prove that Java is Turing-complete you wouldn't look at all the Java programs ever written and try to build a Turing machine with those programs. Instead, you'd use the symbols in the language to write a (new) program that simulates a Turing machine, or a set of functions that suffice to prove Turing completeness. 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?

rcxdude 9y ago
The game of 'Magic: The Gathering' consists of both the rules and the cards available in it (which are written in a kind of language). If you are printing your own cards, most players would agree you are not really playing 'Magic: The Gathering', but your own homebrew game based on it.
- YeGoblynQueenne 9y ago
  Maybe, but if we're doing formal proofs then we're not in the realm of opinion anymore. So the point is to substantiate any claim as to what, exactly, is reasonable to call "the mtg language". I really doubt there's any context in which a language can be formally described as "a limited number of texts"... especially if that language is supposed to be Turing complete (which implies non - finite-ness) ! 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 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.
- YeGoblynQueenne 9y ago
  Just to make it plain. In formal language theory, a language is a set of symbols and a set of rules that determine what is a valid string. 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?