If you don't know what a Turing Machine is, I'd recommend just watching the first few videos on YouTube about it.

They're relevant because a ton of important things have been proven about them, and if you can "embed" a Turing Machine into something, it means many of those theorems apply to whatever you were able to embed it into.

"Embedding" means just arranging a subset of the rules of your system such that they simulate the workings of a a Turing Machine.

A "Universal" Turing Machine is a special case of a Turing Machine that can simulate other Turing Machines, which is to say, it can perform any computation that any computer can perform, given the right inputs.

So if you can embed a Universal Turing Machine (UTM) into your system, it means that your system is capable of simulating any other computer, and can perform any computable task.

"Rogozhin's UTM(2,18)" refers to a Turing Machine with 2 states and 18 symbols, which Rogozhin proved was universal. It's a pretty compact Turing Machine, which is likely why it was selected to be embedded into Magic.

I'm a bit confused about their construction. Cleansing Beam doesn't do what they say it does, and at the moment I can't see how Coalition Victory helps them change the state. I also notice that both Rotlung Reanimator and Xathrid Necromancer are 2/2 creatures, so they're going to get killed by Infest unless they're modified. We'll see if that clears up as I move along. [EDIT: Yes it does.]

OK, wow. They didn't typo by saying Cleansing Beam. They deal with the fact that that card deals -2/-2 to a target creature and all creatures of the same color (instead of what they were claiming it does, add +1/+1 to creatures of that color) with a dizzying array of spells: Privileged Position, a hacked Olivia Voldaren, hacking all Alice's creatures to be of type Assembly-Worker, Steely Resolve, Illusory Gains, and Vigor. So yeah. Sheesh. Ultimately, they end up putting two +1/+1 counters on the side of the tape they're moving away from, and a -1/-1 counter on all creatures representing the tape, which has the intended effect of updating the tape position representation. I assume the convoluted nature of the operation is because Magic doesn't have a direct way of adding +1/+1 counters to all creatures of a particular color, but let me know if you know otherwise.

I love "To ensure that the creatures providing the infrastructure ... aren’t killed by the succession of −1/−1 counters...". This section also takes care of my objection from earlier about the "creatures providing the infrastructure" being small enough to die from the earlier steps, though my specific objection at the time was handled by the Privileged Position.

"D. Changing State" was a bit hard to follow, but I find it helpful to realize that the entire point all all that was just to say that Bob essentially switches between the two states every time it's his turn, (by phasing out one set of Rotlung Reanimators and Xathrid Necromancers, and phasing in another set) so if Alice cycles cards in her Library she can switch her actions into or out of phase with Bob, so different things happen when a different set of infrastructure creatures are phased in.

Haha, I'm guessing Lhurgoyf and Rat were chosen as end-of-tape markers for the L and R in their names?

That was great. I love that the creature type representing a halt is Assassin.