News for hackers. Stuff that matters.
Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Friday November 17, 2017 @04:09AM (#15720391)
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?

Re:Magic: The Gathering Is Turing Complete (2012) by rcxdude on Friday November 17, 2017 @12:14PM (#15723851)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Friday November 17, 2017 @12:48PM (#15724173)
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].

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.

Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Friday November 17, 2017 @12:58PM (#15724274)
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?