I'm assuming you're familiar with the basic idea of what a Turing machine is. There are a few parts to building one in Magic: a tape extending in two directions storing cells of a few different colours; a processing head that can read the current cell's colour, write a new colour and change its state if necessary; and a "virtual" infinite tape extending in both directions.
The full list of all cards on the battlefield and in other zones is on the Cards page; this page won't repeat that in full, but will explain why each card is needed.
The model of the tape is as follows.
A series of Ally tokens controlled by Alex represent the tape to
the right of the current head: the creature one step to the right of
the head is 1 toughness away from dying, the next one over is 2
toughness from dying, etc. A similar chain of Zombie tokens, also
controlled by Alex, represent the tape to the left. The colour of each
token represents the contents of that space on the tape.
The operation "move one step to the left" is represented in this machine by creating a new Ally token, growing all Allies by 1, and shrinking all Zombies by 1. The details are as follows:
When the machine creates a new 2/2 Ally token under Alex's control, four things trigger: Bob's Noxious Ghoul, Cathy's Aether Flash, Denzil's Carnival of Souls, and Alex's Kazuul Warlord. They go on the stack in that order, because it's Bob's turn; so they resolve in reverse order. The Kazuul Warlord adds +1/+1 counters to all Alex's Allies, leaving them one step further away from dying, including making the new one 3/3. Then Carnival of Souls gives Denzil a white mana thanks to False Dawn (he doesn't lose life because of his Platinum Emperion). Then Aether Flash deals 2 damage to the new token, leaving it 1 toughness from dying as desired. And then the Noxious Ghoul, which has been hacked with Artificial Evolution, gives all non-Allies -1/-1, which kills the smallest Zombie. Depending on whether the smallest Zombie was red, green or blue, a different event will trigger. The machine has moved one step to the left.
If the new token had been a Zombie rather than an Ally, a different Kazuul Warlord and a different Noxious Ghoul would have triggered, as well as the same Aether Flash. So the same would have happened except it would be all the Zombies that got +1/+1 and all the Allies that got -1/-1. This would effectively take us one step to the right.
I'm using the simplest Universal Turing Machine, Alex Smith's 2-state, 3-colour machine. Just for reference, Alex's machine says:
The key cards to the heart of the Turing machine are Teysa, Orzhov Scion, Artificial Evolution, and Mind Bend. We use Artificial Evolution and Mind Bend to modify Teysa so that her second ability reads "Whenever another red creature you control dies, put a 1/1 green Ally creature token with flying onto the battlefield."
In fact, we use six copies of Teysa, along with a Mirror Gallery to allow her to coexist with herself. They're modified to read as follows:
At any time, three Teysas are in play: one watching for red deaths, one for green deaths and one for blue deaths. The other three are phased out and have no effect on the game until they phase back in. Which three are phased in corresponds to which state the Turing machine is in.
Teysa's tokens are 1/1 by default. Things work more easily if they're 2/2, which we accomplish with Serra Aviary.
Of course, we can't actually hack Teysa to say "Whenever a blue creature dies, cast Time and Tide, then make a red Ally." Casting an instant as a triggered effect is the greatest hurdle this Turing machine needs to get over.
In order to repeatedly cast this instant, version 4 of the Turing
machine uses Chancellor of the Spires. This is significantly
easier than previous versions which had to use Spellbinder or
Toshiro Umezawa.
We use a hacked Skirk Drill Sergeant to cause the Chancellor of the Spires to
repeatedly enter the battlefield, and Wheel of Sun and Moon to put it
back into Denzil's library. No special tricks need to be done to get
the Time and Tide card back where we want it, as the Chancellor
lets the instant go back into Bob's graveyard when it resolves.
So the Teysas that need to change state actually create tokens that are white and a different creature type, to avoid triggering the normal Kazuul Warlord / Noxious Ghoul pair, and to trigger the state change instead.
Putting it all together, when we need to change state, this is what happens:
Teysa makes a white
Dragon, Dryad, or Drake
token for Alex. The assorted Crusades, Triumphs and Plagues make it an Advisor Sphinx and 1/1.
Cathy's Aether Flash triggers, as does Denzil's Carnival of Souls.
Stack:
...cAF dCoS
Carnival of Souls's ability resolves, gives Denzil a white mana
thanks to False Dawn. His life total doesn't change thanks to Platinum Emperion.
Stack:
...cAF
Aether Flash's ability resolves, killing the Dragon/Dryad/Drake.
This triggers one of Bob's three Rotlung Reanimators according to
whether it was an Dragon, Dryad or Drake that died. But since all Dragons,
Dryads and Drakes are also Sphinxes, on top of that
on the stack goes Denzil's hacked Skirk Drill Sergeant.
Stack:
...bRR dSDS
Skirk Drill Sergeant's ability resolves.
Denzil pays the 2R cost with WWW thanks to False Dawn. Skirk Drill
Sergeant finds the only card in Denzil's library is a Chancellor of the Spires, and because he's been hacked to like Sphinxes, the Drill
Sergeant drops it onto the battlefield. Alex's Gather Specimens
means it enters under Alex's control.
When Chancellor of the Spires enters the battlefield, three things
trigger: Cathy's Aether Flash, Denzil's Carnival of Souls, and
Alex's Chancellor itself. The only target for the Chancellor's
triggered ability is Time and Tide.
Stack:
...bRR cAF dCoS aCotS
Chancellor's ability resolves and Alex casts Time and Tide (putting it on the stack).
Stack:
...bRR cAF dCoS aToT
Time and Tide resolves, returning to Bob's graveyard. All Teysas
phase in or out.
Stack:
...bRR cAF dCoS
Carnival of Souls's ability gives Denzil a mana.
Stack:
...bRR cAF
Aether Flash's ability resolves, dealing 2 damage to Chancellor of
the Spires. Thanks to the Engineered Plagues, this is enough to kill it. State-based actions try to put it
into Denzil's graveyard, but actually send it to bottom of Denzil's
library thanks to Wheel of Sun and Moon. This doesn't trigger
anything, because it's not going to the graveyard.
Stack:
...bRR
Finally, Bob's Rotlung Reanimator's ability resolves, making a
red, green or blue Ally or Zombie token depending on whether the white
token from before was a Dragon, Dryad or Drake. Because Alex cast
Gather Specimens earlier this turn, the token arrives under Alex's
control (so that Kazuul Warlord can see it). This triggers a Kazuul
Warlord and a Noxious Ghoul as well as Aether Flash, and the usual
processing continues.
Finally, what do we do if we run out of initialised tape? If the Turing machine moves to a space that hasn't been visited before, the normal processing loop will come to an abrupt halt. The default colour of tape on the Turing machine we're using is blue, so we need a simulation of an infinite tape of empty blue spaces – that is, we need to make the machine act as if there were a blue Ally or Zombie token that just got killed.
This is where the Sentinel on the bottom of the stack comes in. Bob's other Rotlung Reanimator will make a blue Illusion (under Alex's control due to Gather Specimens). This Illusion will not trigger any Kazuul Warlords or Noxious Ghouls, so it will immediately die to Aether Flash. This triggers Teysa C or F just as if there had been a blue Ally or Zombie die. And it also triggers Bob's Rotlung Reanimator to put an ability at the bottom of the stack to make another blue Illusion, ready for the next time we exceed the bounds of the tape.