MTG is Turing Complete

Legacy

Ender_Creeper_11

Logic processing (11)

• 1x Cleansing Beam
• 1x Cloak of Invisibility
• 1x Dread of Night
• 1x Fungus Sliver
• 1x Illusory Gains
• 1x Infest
• 1x Privileged Position
• 1x Rotlung Reanimator
• 1x Soul Snuffers
• 1x Steely Resolve
• 1x Vigor

Remove choices (2)

• 1x Blazing Archon
• 1x Recycle

Draw Rest of Deck (4)

• 4x Staff of Domination

Edit Card Control (1)

• 1x Donate

Edit Cards (4)

• 1x Artificial Evolution
• 1x Glamerdye
• 1x Olivia Voldaren
• 1x Prismatic Lace

Simplify setup (3)

• 1x Claws of Gix
• 1x Djinn Illuminatus
• 1x Reito Lantern

Change state (2)

• 1x Mesmeric Orb
• 1x Xathrid Necromancer

Forced play device (2)

• 1x Wheel of Sun and Moon
• 1x Wild Evocation

Setup tape (2)

• 1x Capsize
• 1x Riptide Replicator

Edit Card Phase (1)

• 1x Reality Ripple

Halting device (3)

• 1x Choke
• 1x Coalition VictoryGC
• 1x Prismatic Omen

Infinite Mana Device (12)

• 4x Gemstone Array
• 4x Grim MonolithGC
• 4x Power Artifact

Bootstrap (8)

• 4x Ancient TombGC
• 4x Lotus Petal

Cleanup after setup (2)

• 1x Fathom Feeder
• 1x Karn Liberated

Make Token Copies (2)

• 1x Memnarch
• 1x Stolen Identity

Infinite tape device (1)

• 1x Shared Triumph

---

Deck that can create a Turing Machine out of Magic the Gathering. Theoretically with this deck, one could setup a game state in which it becomes possible to compute ANY computable problem in finite time. The game state, once set up, is one such that play continues effectively autonomously, following a program set up in the game state, until a point which the Turing Machine Halts, in which case, the executing player wins the game. The final observed game state may then be interpreted as the result of the program.

Please read the following paper to learn more: Deck Source & Paper describing Turing Completeness of MTG

This deck Should not be taken as a serious Legacy Tournament Deck. It requires a perfect opening hand to execute, as well as an extended period of time to execute the entirety of the program. If the program is not set up such that the turing machine would eventually halt, then the game enters an infinite sequence of mandatory actions and therefore becomes a draw by 104.4b of the Magic Comprehensive Rules (But note that the halting problem applies)

Date added	5 years
Last updated	5 years
Legality	This deck is Legacy legal.
Rarity (main - side)	2 - 0 Mythic Rares 37 - 0 Rares 14 - 0 Uncommons 7 - 0 Commons
Cards	60
Avg. CMC	3.16
Tokens	Copy Clone, Zombie 2/2 B
Folders	Nifty Ideas, Meme Decks, turing