Me: "It's O(n), but the constant in the front is enormous, so it's usually totally impractical"
?
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.
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.
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).
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.
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?
Mainly related to jealousy in my experience, with people trying to detour you with a myriad of concerns
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...
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.
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?
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.
[0]https://en.wikipedia.org/wiki/Median_of_medians