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?
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.
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.