There lots of maybe-valid criticisms about this setup- oh, you have to use so many game mechanics to make this work; you need to have 4 players all working together to do it and get just the right conditions; this can never happen in real play.
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.
The paper you've posted: "The Median of Medians (also known as BFPRT) algorithm, although a landmark theoretical achievement, is seldom used in practice because it and its variants are slower than simple approaches based on sampling."
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.
I'm not saying QuickSelect has a large constant. I am saying the median of median O(n) algorithm, which again is not QuickSelect, has a large constant.
And I am saying that when you combine the two you get an algorithm with a small constant in practice and guaranteed O(n) behavior in the worst case.
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.
That's very cool. However, the anecdote I was sharing for comparison purposes specially referred to the median of median algorithms. This was also many years ago, long before the paper above was written.
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.
Introselect is a more complex version of the same idea.
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).
I remember my algorithms class wasting like a week and a half going over that. I'm still a little bitter. There's only a few courses that I would have wanted a refund on my tuition for, and that's one of them.
I'm not a domain expert, but I would assume that "approaches based on sampling" could be O(1). If so, the slowness would be based on the scaling, not on the constant.
If you keep the number of samples constant (so that you can have O(1) time) then the quality of the estimate goes down with the number of items in the collection. To keep the quality constant, you need number of samples to scale with the size of the collection.
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.
Not necessarily, using k samples you can estimate the mean of i.i.d. samples with a variance of 1/k the sample variance. Note that this is independent of the sample distribution, in particular it's also true if you're drawing from some fixed collection, regardless of its size.
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?
Quickselect has an O(n^2) worst case, unless you use a variant like Tarjan's median-of-medians algorithm for selecting the pivot. And that does have awful constant factors.
Yeah, this was the specific algorithm I meant. O(n) time, but in my undergrad implementation, it wasn't useful with less than billions of items, vs just sorting and selecting with highly optimized sorts.
If you are dealing with numbers, then you can do this is true O(n) time with radix-select. (Basically do a MSB radix sort and only do subsequent passes in the bucket where you know k must be).
There are two types of algorithms . Ones we can implement with reasonable time. Then the others where we can’t implement in a reasonable time at this moment.
Ya, the obligatory pendantics (concern trolling, nit picking, Eeyore-isms) is frustrating. I have a core group of nerd friends that are fun to play catch with. Any more, I’ve stopped voicing my crazy, weird, random, fun ideas to most people.
Well, the proof is contrived, but that's not the point: it's also unnecessary
and it may also be insufficient.
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.
A formal system, in this case the game, is Turing complete if it can be used to implement a Turing machine. Complaining about using only a limited and very specific subset of available cards in a contrived way is like saying that a computer is not a computer because a large number of transistors aren't part of it, and if I rewire it randomly it ceases to work.
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.
>> 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.
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.
For Turing completeness it is not sufficient to demonstrate that a system has "a store". The store needs infinite capacity and random access. Infinite capacity alone is not enough - a stack has infinite capacity but a stack machine has demonstrably weaker expression power than a Turing machine: https://en.wikipedia.org/wiki/Pushdown_automaton
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.
There's no limitation on the size of the M:tG Stack, so it is infinite. Also, that M:tG uses a Stack as a store doesn't make it a pushdown automaton. For a pushdown automaton you need the stack to control decisions, but that is not the case here- there's still player actions and the effects of cards in the game etc.
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.
"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.
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?
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.
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) !
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.
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.
For that matter, a physical digital computer has a bounded number of states it can be in, so it can't be Turing complete at all, if you're going to be really pedantic.
You're only allowed to say MTGO is not Turing complete if you also agree that Java is not Turing complete (because the 32-bit JVM has bounded memory it can access).
There's also the infamous video of (well-known professional player) Luis Scott-Vargas "breaking" MTGO by causing the game to wind up in a non-terminating loop of mandatory actions:
Its effect is that, when it comes into play, you choose a non-land card in play that gets exiled (removed from play) for as long as Oblivion Ring stays in play, then gets returned once Oblivion Ring leaves play. This game devolves into a situation where there are three Oblivion Rings and no other non-land cards, so: Ring 1 exiles Ring 2, which returns Ring 3, which exiles Ring 1, which returns Ring 2, which exiles Ring 3, which returns Ring 1, which exiles Ring 2, and so on to infinity. The rules state that when a loop like this occurs (which is not often in real play), the game is an automatic draw.
Yes - old, rare cards (especially powerful ones that are now considered "broken") have only risen in value.
They're also quite provocative. Once every few years I'll break out my very, very old "power nine" deck and play with it at the local game store. All games stop. Everyone comes to look. People take pictures.
I hope you play without sleeves and watch the other players shrivel... From time to time you should mumble: yes peasants! I'm that rich :) ahashahahahahahahzha
holy crap I didn't realize these were worth that much, I have boxes of these in my closet right now with cards from Unlimited/Legacy to Tempest(maybe some newer but i forget what the releases were called).
It is highly dependent, but if you're curious you can check a website like tcgplayer.com and enter your cards in to get an idea. You'd want to look at the market value, rather than high/mid/low.
Also consider that if you did want to sell, selling to a store drastically cuts value. Individual sales aren't without their share of problems either.
I'm heavily involved in MTG, so if you did have further questions feel free to reach out.
I couple of years ago, i found some old random magic cards from like revised with some dual lands and tossed it because I thought that they were still worth like $10 a piece.. turns out I threw away like $1500 worth of cards :(
My original collection was stolen in 1995 and would be worth as much as McMansion today. At the time it was worth about $5000.
As someone that does not understand the rules of Magic, how do they get around the fact that a Turing machine requires infinite memory? Presumably a particular game of Magic has a finite set of cards and probably states too?
Many Magic cards can create "tokens" which don't count as cards, but can operate in the same way as cards in many ways.
You can have as many tokens as you can create. The MTM (Magic Turing Machine) seems to rely on this.
It's actually within the rules to "go infinite" with tokens. For example, you have a Foo which taps (is spent) to create a Bar token. The Bar token can untap (reset) Foo. Since you can do this as much as possible, within the rules you effectively just simulate that you can repeat the combo, pick a number (100, 1 million or 1 Googolplex), and you have that many.
The proof is much more complex than that, using various creature types (zombie, rats, etc.) and other game states, but that is how the infinite memory problem can be overcome.
It's also worth noting that the infinite memory requirements is often ignored when showing Turing Completeness.
(I play a lot of Magic and just took a glance at the page)
+1/+1 counters on Zombies represent the tape to the right.
+1/+1 counters on Yetis represent the tape to the left.
Whenever you reach the "end of Tape" (ie: All your Zombies are now Yetis), there's a trigger that creates a new Zombie token. Effectively creating "infinite tape". I didn't read to see how it worked on the "Yeti side", but I presume its the same concept.
Moving the tape back and forth is about putting -1/-1 counters on Yetis and +1/+1 counters on Zombies, or vice versa. Death triggers convert Yetis into Zombies and vice versa.
There are 18-states representing the "tape head" (which I presume to be the current creature with zero counters on it). I haven't really looked into how it works, but "Halt" state is pretty amusing actually. The "Halt" state kills all players, which "Halts" the program.
Yes, computers are not Turing machines but finite state machines. But in practice, this is not very useful since the number of states of a computer is huge, so, Turing machine is a good model for computers. In math, we're not interested in physical objects but models and it turns out the study of Turing machines can be applied to physical computers. When you think of computer, you do not think it as finite state machine, but as a Turing machine. Maybe if you had a machine with 1KB memory, you could think it as a finite state machine, if it's more useful.
Another thing is, most algorithms people deal with are O(1) since people are interested in ints which can represent -2^63 to 2^63-1. But this is just an abuse of terminology, an algorithm that tries all 2^64 combinations would be a very impractical O(1) algorithm. So, we instead use a different model, and pretend integers are arbitrarily long and their length is O(logn) bits. This is now a better model for physical computers.
Sure. But anything a turing machine could calculate in finite time can be calculated using finite memory, so this doesn't matter unless you're trying to compute things that don't end.
I quit playing Magic in 1999 when my 4 friends and I found out we were playing by the wrong rules.
We went into town, to a tournament at a comic shop, and saw the games taking 20 minutes. Ours took 1-2 days.
We tried what was, to us, the “new rules” and we were disappointed, gave up. It was a big blow. Suddenly the cards were less enchanted, the decks were less sacred. Maybe if I had understood the Turing completeness of Magic, I would have had it in me to start a tournament under our rules. Well, I still could if I had written them down. I’m pretty sure they were the best rules.
Maybe it was upkeep-related? There's the phrase "untap, upkeep, draw" and all the "at the beginning of your next turn" cards refer to the upkeep phase if I'm not mistaken, maybe putting upkeep before untap or after draw would lead to some weird long-term mechanics.
I don't want to throw anybody under the bus here, but basically one friend taught the other friends, and I was one of the students. Nobody complained or blamed him, though. We played for about a solid year and it was an amazing experience.
A pencil and paper is Turing Complete. A bunch of rocks in a grid is Turing Complete.[1]
Sorry to be an ass but I can't even guess how many "X is Turing Complete" things I've seen over the years. Turing's point wasn't to define what can be a computer, it was to define the limits of computation itself. Which is a far more interesting topic, hence my irritation with this post.
No, the interesting point is that the rules of MtG are Turing Complete, not that you can express something that's Turing Complete using them as your notation. That wouldn't be interesting at all.
The author admits he has constructed an artificial scenario under which a Turing Machine is generated. This is exactly the same as using the rules of MtG as a notation to create a machine.
A generalized set of the rules for the game Go is Turing Complete. A generalized set of the rules for the game Go Fish is Turing Complete.
Okay, so all you've said is "Go is, interestingly, also Turing Complete". That is interesting and worth-posting-about information. In an attempt to illustrate the futility of the Mtg example with a Go example, you have in fact merely illustrated that in addition to Mtg, Go is ALSO interesting to look at.
Mtg can be shown to be Turing Complete in one (of quite a few, actually) subset of rules. That's cool, and unexpected to many, and worth reading about.
And that's true for any other example of things not usually associated with programming.
(Turing completeness is an algorithmic property, not a "thing" property, so a pencil and some paper, or a bunch rocks, are certainly not Turing complete: you need procedural rules as well, something Mtg has no shortage of)
I know I shouldn't bite, but I just want to so bad...
>so all you've said is
Actually what I said was "a generalized set of the rules" for Go is Turing Complete. Go in itself is not, because the end-state of the game is indeterminate. Just as a "regular-ass" game of MtG without a very specific and artificial construction is not Turing Complete, in and of itself.
>That's cool
I can appreciate stamp collecting, and I don't want to say that it's an invalid use of time. There are plenty of worse hobbies. But my point is that any of an infinite, arbitrary, and inconsequential number of conceivable systems are "Turing Complete," and personally I don't find this very compelling.
How many books in the Library of Babel[1] describe a Turing Complete system?
>Turing completeness is/is not
I stated as much in a comment below, or you could have inferred the same by my interpretation of the XKCD comic, but thanks for assuming I'm incompetent and acting in bad faith.
Are you making the distinction that most MtG decks are not Turing-Complete? Is that what you mean by "specific and artificial construction?"
I think most people assumed that Turing-Completeness requires a specific and artificial construction, which is where the disconnected (and downvotes) are coming from. Especially for something wasn't previously believed to be a model of computation at all, much less a Turing-Complete one.
You seem to be taking a very hostile stance against what, a detailed and researched article about a project you don't deem worthy enough for your interest?
> The author admits he has constructed an artificial scenario under which a Turing Machine is generated. This is exactly the same as using the rules of MtG as a notation to create a machine.
An artificial scenario which is achievable under normal play, and the only variation required by the human players being that when offered a choice, they choose affirmative.
> A generalized set of the rules for the game Go is Turing Complete. A generalized set of the rules for the game Go Fish is Turing Complete.
Do you have references for those? I would be interested in seeing how they simulated the tape.
True, but this is a game with no intention of being Turing complete. Yet there is a set of cards and mechanics within an "innocuous" game that resulted in a Turing Machine.
I believe GP's point is that Magic: The Gathering was not
intended to be a turing-complete set of rules and cards.
I.e., the game design was _intended_ to be entirely decidable. Indeed, certain game rules discuss what happens when events trigger each other in a loop - and if the loop is non-halting, the game ends in a draw. This rule is only meaningful if the halting problem for M:tG is decidable!
However, in creating enough "relatively simple" cards, most of which are of the form "when one thing happens, another thing then happens", the designers of M:tG have managed to _accidentally_ create a non-decidable system.
Sure, this particular example is contrived, but it has the implications that a non-contrived game state could find itself in an undecidable state! It is theoretically possible that a natural, tournament-level game could reach a state where it can't be decided if one player or the other wins, or if it's a draw. (Or, at minimum, deciding the outcome of the game might require sufficiently convincing a tournament official of your mathematical proof that the game in fact will halt , within some known finite time).
The situation you describe isn't even that farfetched. There is a moderately popular deck called Four Horsemen that depends on repeating a set of steps to repeatedly shuffle your deck until the cards happen to be arranged in a sequence that allows you to win.
"Shahrazad" had the potential to make impossibly long games, possibly even undecidable with the right combo. It has been used to force draws by stalling games.
For that reason, it is now banned in all tournament formats. In fact, it is the only "normal" card to receive this treatment.
With some contrieved meaning of the cards, which has nothing to do with the "meaning of the card" in Magic the game, like "State B, Colour 16: Stay in state B, colour this space 18, move one step right." it recreates a complicated and arcane turing machine.
That's like saying a file on your computer is just a "contrived meaning" of the way magnetic domains are arranged on some glass platters in your hard drive.
Those aren't new rules for the cards that they're just contriving out of thin air. When it says that's what it "actually says", it means that's what the net effect of the card's actual text is in the environment that's been set up. It's just a rhetorical shortcut to help explain how the system works. All the cards are using the correct text as normal.
This is like saying, "Draw go" isn't talking about MTG. It's shorthand for all of the steps that you'd need to complete. Just like someone playing an Eggs deck is going to say "Casting KCI + IW, draw 2, float 2" or "Here is the main loop. I'm going to do that until I hit banefire, then hit you for infinite damage."
What's interesting is actual MTG gameplay uses a HUGE amount of shortcuts on every play, because saying every single thing you and the opponent have to do during each step and phase would be incredibly time consuming.
Well, that gets weird. It can have shortcuts and also won't have shortcuts.
If you play Commander or multiplayer, then its usually a heck of a lot less formal. Ive also played some local tournament games where the players were good-natured and we all just had fun.
Then I've played some tournaments locally and at Gencon that were methodical and clockwork style "Please indicate what you did, step by ste-COUNTER". Or you get the priority police up and running, where you have to explicitly pass priority. I hate those games with a passion - it just drains the fun out via rules-lawyering.
I've not played in a few years, primarily because the game was feeling much more like 'loot crates' that I've railed against prior. And with $3.50/pack, I didn't feel like I was getting enjoyment. You either buy buy buy, or get left in the dust and destroyed in games because you didnt buy buy buy.
>"Please indicate what you did, step by ste-COUNTER"
What's the advantage over simply specifying the moment you wanted to react out of the last batch of actions (like a normal person)? If the opponent skips too many steps and gives up some critical information as a result -- his problem.
Because that leads to bad feels; did you counter X because you know I have Y in my hand now? I always try to explicitly pass priority after spells even in causal settings when I mean to.
In a way, its an iterated prisoner's dilemma. Sure, I can construct a "infinite beatdown deck" that you lose 99% of the time. And guess what? I'll win.
And that next game, they'll say "ditch that deck or you aren't playing".
These days, I play explicit decks that have a neat theme and good win conditions (I have 2 decks left). They dont use infinite combos (they win, but are unfun), and I play to have a good time. If I lose, it was because I had some good threats and a blast of a game.
Words they've used like "State B, Colour 16: Stay in state B, colour this space 18, move one step right" are just mnemonics, for the sake of keeping track of information relevant to Turing completeness, that could be replaced by a description of whatever is actually happening in the game.
Thanks, didn't know "colour this space 18" was a concept in MTG now, I haven't played for 2 decades I assume (stopped before Legends, no clue what came afterwards).
Isn't what states "mean" irrelevant to whether it's a Turing machine? I was under the impression that as long as it can simulate a Turing machine (even an arcane or complicated one) is Turing complete and the state could be stored in anything (it's not like electricity has some special property that makes it better for Turing machines)
It is precisely this ability to map seemingly arbitrary and meaningless physical manifestations of turning machines to the abstract that provides the concept so much power. By being able to provably map the implementation to the concept you're able to get all the "benefits" of the concept without having to individually prove them in your implementation where it might be really difficult or just time consuming to prove everything individually.
This, coincidentally, is the same reason mathematics is so obsessed with isomorphisms, homeomorphisms, homomorphisms etc. They are all different ways of saying "this thing stays the same, even when it changes" which many times means that things proven in a place where it's easy to prove are maintained in places where it's very difficult or even impossible to prove (absent the isomorphism).
>it's not like electricity has some special property that makes it better for Turing machines
Transmission, storage with magnetic interactions of electrical actions, small size of components, speed of transmission -- aren't these properties that make for more practical Turing machines?
Parked cars are going to take ages to do anything useful with, no.
This is just a miscommunication of what "better" means in this context.
No one disputes that a modern computer implementing a Turing machine is going to calculate faster than manually manipulating MTG cards.
However, better here means 'more expressive'. Turing completeness is concerned with whether or not a computational system is 'universal' or not. In other words, whether that computational system can compute everything that another computational system could. If two systems can both be shown to simulate a Turing machine, then that means that those systems could compute the same exact set of things (given enough time).
So with regards to expressiveness (or the things a system could theoretically compute), since a modern computer can implement a Turing machine and a MTG game can implement a Turing machine, they are both the same, and thus neither is 'better'. In other words, the addition of electricity doesn't effect what a system could theoretically compute.
More practical, yes. However, I believe the original poster's intent was that neither one is a "preferred" implementation from the perspective of the concept itself. There's no necessary tie between a Turing machine and electromagnetic fields. It's just that's what is easiest for us humans to use to implement it.
Keywords "practical" and "useful". No one advocates parking-lot Turing machines for actual usage, but the fact is electronics only gives you speed and size improvements, while expressiveness remains the same.
I can forgive the extremely contrived decks, but using a card to completely change the behavior of the majority of your cards doesn't mean the game itself is Turing complete. If anything, this is just showing how you can utilize Magic game mechanics to create a Turing Machine.
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