One of the hardest parts of creating a Turing machine in Magic is representing the tape. This needs an ordered sequence of objects in the game, and this is a slight problem, because most Magic zones aren't ordered. The battlefield doesn't have any concept of "the next space to the left": there's no inherent order to objects on the battlefield. Some Magic zones are ordered: the stack, the graveyard and the library. However, modern Magic cards don't care about the order of the graveyard; there aren't enough cards that do care to form a proper machine using the graveyard as half of the tape. There are many cards that care about the order of cards in the library, but there's another problem: The tape needs to stretch for potentially millions of spaces in both directions. It's clear that it needs to be represented by tokens of some kind rather than actual cards. And tokens can't exist in the graveyard or library.
It's just about possible to use the stack as one half of the infinite Turing tape. But it's pretty fiddly, and since all players share one stack, you still need something to do for the other half of the tape.
The answer is that you can impose a kind of order on objects on the battlefield. The game can distinguish one object from another in several ways, but only a couple of these ways can scale to millions of spaces. The game does have a concept of timestamp order, where the most recently created effect gets to trump other older ones in certain circumstances. It might be possible to assemble a Turing machine using this concept.
However, an easier approach is to use a large number of creature tokens of different sizes. If there's just one Zombie creature that's 1/1, one that's 2/2, one that's 3/3 and so on, then the operation "give all Zombies -1/-1" will kill one creature token, and the game can notice the properties of the token that died. The former 2/2 will now be a 1/1, the 3/3 will be a 2/2, and so on. We have effectively taken one step towards the largest creature. We can step in the other direction by putting a +1/+1 counter on all Zombie creatures. (I'm grateful to Edwin Thomson for the idea to use Kazuul Warlord in this way.)
I really wanted the machine to have all the execution fall out as triggered abilities. I don't want any "rules" telling the players how to behave like "If you can activate Isochron Scepter, you immediately do". But the implementation of the heart of the machine uses the Magic concept of "being phased out" to represent the two states of the Turing machine, and we need to repeatedly switch states. The only printed Magic card that does this is Time and Tide. Unfortunately, this is an instant.
However, there are just a handful of Magic cards that let you cast an instant in a triggered way. When I was first creating the Turing machine in 2010, the three potential ways I found were Toshiro Umezawa, Spellshift, and Spellbinder. Turing Machine version 2 used Spellbinder, and version 3 used Toshiro Umezawa. However, New Phyrexia brought Chancellor of the Spires, which makes this process significantly easier.
But Chancellor of the Spires still isn't especially easy to repeatedly trigger. It required a Skirk Drill Sergeant to drop it onto the battlefield, which in turn requires mana payment, and the only suitable triggered way to add mana was Carnival of Souls, with the help of False Dawn. (Mycosynth Lattice would have allowed us to use Mana Echoes, except that Mycosynth Lattice also makes all creatures colourless which stops Teysa from working!)
Version 4 tightens up the number of choices the players need to make even further. Version 3 of the machine used to have Riftsweeper and Carnival of Souls controlled by the same player, which meant that player had to make an arbitrary choice which order to stack the triggered abilities each phase change. The choice didn't matter, but it was still a choice the game asked a player to make. I circumvent this in version 4 by using Gather Specimens so that the triggers from Chancellor of the Spires and Carnival of Souls are controlled by different players, so the rules of the game force an order upon them with no player input required.
There's no such thing as infinity in Magic. You can never have an infinite amount of any resource, just an arbitrarily large amount of it.
For our purposes, this means that however large a Turing tape we prepare before execution, the machine may need more of it. So we need to make the engine be capable of detecting when it tries to move to a space that doesn't yet exist, and initialise it at that point to the tape's default colour.
If the machine's execution is all playing out as a sequence of triggered abilities within a single phase of the game (as in this Chancellor of the Spires version), then you can just have an item at the bottom of the stack that kicks the machine back into execution and puts another copy of itself on the stack. Rotlung Reanimator is perfect for this: we hack it so that whenever a blue Illusion dies, it makes another blue Illusion, and then we have an infinitely self-sustaining foundation to re-trigger the main machine.