Introduction

Magic: The Gathering, first released by Wizards of the Coast in 1993, is a card game with thousands of different cards. Each card carries its own rules text, and the rules of the game are what you get when all of those texts are layered on top of each other. Players are used to thinking of this as a source of strategy. Computer scientists noticed it is also a source of computational power.

In 2019 Alex Churchill, Stella Biderman and Austin Herrick posted the paper Magic: The Gathering is Turing Complete (arXiv 1904.09828; a peer-reviewed version appeared at the FUN with Algorithms conference in 2021). They showed how to build a game of Magic, with ordinary cards and a standard-size deck, that simulates an arbitrary Turing machine. The first player wins exactly when the simulated machine halts.

That is a strong statement. A Turing machine is the standard mathematical model of a computer, and the halting problem says no algorithm can decide in general whether such a machine ever stops. If a game of Magic can run any Turing machine, then no algorithm can decide, for every position, which player has a winning strategy. The authors present this as the first result showing that a real-world game, one that people actually play, has non-computable optimal play.

The construction is not a practical way to compute anything: one step of the simulated machine takes many turns, and nobody would build this deck to run a program. Its value is as a proof about the game itself, and as a vivid example of how easily complexity piles up in a system whose parts interact freely.

A Turing Machine on Token Cards

The Magic construction stores the machine's tape as a row of creature tokens, one token per cell. The demo below draws the same picture: each cell holds a blue or orange token (the symbols 0 and 1) or an empty slot (a blank), and a marker shows where the head is and which state the machine is in. The machines are small ones, not the universal machine used in the paper, but they follow the same rules.

<p class="hint">A Turing machine reads a tape of tokens, one cell at a time. Blue and orange tokens are the symbols 0 and 1; an empty slot is a blank. The marker shows the head and its state. Pick a machine and run it.</p>
<div class="presets" id="presets" role="group" aria-label="Machine presets">
  <button type="button" data-p="inc">Binary +1</button>
  <button type="button" data-p="add">Unary 3+2</button>
  <button type="button" data-p="bb3">Busy beaver 3</button>
  <button type="button" data-p="bb4">Busy beaver 4</button>
  <button type="button" data-p="loop">Never halts</button>
</div>
<p class="desc" id="desc"></p>
<div class="headrow" id="headrow"></div>
<div class="tape" id="tape" aria-label="Tape cells around the head"></div>
<div class="stats">
  <span>Steps <b id="s_steps">0</b></span>
  <span>State <b id="s_state">-</b></span>
  <span>Ones <b id="s_ones">0</b></span>
</div>
<div class="btns">
  <button type="button" id="step">Step</button>
  <button type="button" id="run">Run</button>
  <button type="button" id="skip" class="ghost">Run to budget</button>
  <button type="button" id="reset" class="ghost">Reset</button>
  <label class="bud">Step budget <select id="budget">
    <option value="25">25</option>
    <option value="100">100</option>
    <option value="1000" selected>1000</option>
    <option value="100000">100000</option>
  </select></label>
</div>
<div class="verdict" id="verdict" role="status" aria-live="polite"></div>
<table class="rules" id="rules" aria-label="Transition table"></table>

:root { --bg: #ffffff; --fg: #1f2933; --muted: #52606d; --line: #cbd2d9; --panel: #f0f4f8; --accent: #1d3557; --accent-fg: #ffffff; --t0: #3a7bd5; --t1: #e8912d; --tfg: #ffffff; --ok: #0a7d33; --warn: #b4540a; }
@media (prefers-color-scheme: dark) {
  :root { --bg: #14181d; --fg: #e4e9ee; --muted: #9aa8b6; --line: #394552; --panel: #1e252d; --accent: #8fb4e8; --accent-fg: #10151a; --t0: #4f8fe0; --t1: #f0a24a; --tfg: #10151a; --ok: #4cc27a; --warn: #f0a24a; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 2px; }
.hint { font-size: .85rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.4; }
.presets { display: flex; flex-wrap: wrap; gap: .35rem; margin-bottom: .4rem; }
.presets button { font: 600 12px system-ui, sans-serif; padding: .35rem .6rem; border: 1px solid var(--line); background: var(--panel); color: var(--fg); border-radius: 999px; cursor: pointer; }
.presets button.active { background: var(--accent); color: var(--accent-fg); border-color: var(--accent); }
.desc { font-size: .8rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.35; min-height: 2.2em; }
.headrow, .tape { display: grid; grid-template-columns: repeat(11, minmax(0, 1fr)); gap: 3px; }
.marker { text-align: center; font: 700 13px ui-monospace, monospace; color: var(--accent); }
.marker::after { content: "\25BC"; display: block; line-height: 1; font-size: 11px; }
.marker.stop { color: var(--warn); }
.cell { aspect-ratio: 3 / 4; max-height: 64px; border: 1px dashed var(--line); border-radius: 6px; display: flex; align-items: center; justify-content: center; background: var(--panel); }
.cell.here { border: 2px solid var(--accent); }
.tok { display: inline-flex; align-items: center; justify-content: center; font: 700 15px ui-monospace, monospace; color: var(--tfg); border-radius: 5px; }
.cell .tok { width: 84%; height: 88%; }
.tok.t0 { background: var(--t0); }
.tok.t1 { background: var(--t1); }
.tok.t_ { background: transparent; }
.stats { display: flex; gap: .9rem; flex-wrap: wrap; font-size: .85rem; margin: .5rem 0; color: var(--muted); }
.stats b { color: var(--fg); font-family: ui-monospace, monospace; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; }
.btns button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid var(--accent); background: var(--accent); color: var(--accent-fg); border-radius: 8px; cursor: pointer; }
.btns button.ghost { background: transparent; color: var(--accent); }
.bud { font-size: .8rem; color: var(--muted); }
.bud select { font: inherit; background: var(--panel); color: var(--fg); border: 1px solid var(--line); border-radius: 6px; padding: .2rem; }
.verdict { margin: .6rem 0; padding: .45rem .6rem; border-radius: 8px; background: var(--panel); font-size: .85rem; font-weight: 600; line-height: 1.35; min-height: 2.4em; }
.verdict.ok { color: var(--ok); }
.verdict.warn { color: var(--warn); }
.rules { border-collapse: collapse; font: 12px ui-monospace, monospace; width: 100%; max-width: 360px; }
.rules th, .rules td { border: 1px solid var(--line); padding: 3px 6px; text-align: center; }
.rules td.on { background: var(--accent); color: var(--accent-fg); }
.rules .tok { width: 18px; height: 18px; font-size: 11px; }
.rules .tok.t_ { border: 1px dashed var(--line); }

const PRESETS = {
  inc: { states: ['C'], start: 'C', symbols: ['_', '0', '1'], tape: '1011', head: 3,
    rules: { C: { '1': ['0', 'L', 'C'], '0': ['1', 'L', 'H'], '_': ['1', 'L', 'H'] } } },
  bb3: { states: ['A', 'B', 'C'], start: 'A', symbols: ['_', '1'], tape: '', head: 0,
    rules: { A: { '_': ['1', 'L', 'C'], '1': ['1', 'L', 'H'] }, B: { '_': ['1', 'R', 'B'], '1': ['1', 'R', 'A'] }, C: { '_': ['1', 'R', 'C'], '1': ['_', 'L', 'B'] } } },
  bb4: { states: ['A', 'B', 'C', 'D'], start: 'A', symbols: ['_', '1'], tape: '', head: 0,
    rules: { A: { '_': ['1', 'R', 'B'], '1': ['1', 'L', 'B'] }, B: { '_': ['1', 'L', 'A'], '1': ['_', 'L', 'C'] }, C: { '_': ['1', 'R', 'H'], '1': ['1', 'L', 'D'] }, D: { '_': ['1', 'R', 'D'], '1': ['_', 'R', 'A'] } } },
  add: { states: ['A', 'B', 'C'], start: 'A', symbols: ['_', '1'], tape: '111_11', head: 0,
    rules: { A: { '1': ['1', 'R', 'A'], '_': ['1', 'R', 'B'] }, B: { '1': ['1', 'R', 'B'], '_': ['_', 'L', 'C'] }, C: { '1': ['_', 'L', 'H'], '_': ['_', 'L', 'H'] } } },
  loop: { states: ['A', 'B'], start: 'A', symbols: ['_', '0', '1'], tape: '', head: 0,
    rules: { A: { '1': ['0', 'L', 'A'], '0': ['1', 'R', 'B'], '_': ['1', 'R', 'B'] }, B: { '0': ['0', 'R', 'B'], '1': ['1', 'R', 'B'], '_': ['_', 'L', 'A'] } } }
};
function makeMachine(key) {
  const p = PRESETS[key];
  const tape = new Map();
  for (let i = 0; i < p.tape.length; i++) if (p.tape[i] !== '_') tape.set(i, p.tape[i]);
  return { p, tape, pos: p.head, state: p.start, steps: 0, halted: false, last: null };
}
function stepMachine(m) {
  if (m.halted) return false;
  const sym = m.tape.get(m.pos) || '_';
  const r = m.p.rules[m.state][sym];
  m.last = [m.state, sym];
  if (sym === '_') m.tape.delete(m.pos);
  if (r[0] === '_') m.tape.delete(m.pos); else m.tape.set(m.pos, r[0]);
  m.pos += r[1] === 'R' ? 1 : -1;
  m.steps++;
  if (r[2] === 'H') m.halted = true; else m.state = r[2];
  return true;
}
function countOnes(m) { let n = 0; m.tape.forEach(v => { if (v === '1') n++; }); return n; }
function tapeString(m) {
  if (!m.tape.size) return '';
  const ks = [...m.tape.keys()]; const lo = Math.min(...ks), hi = Math.max(...ks); let s = '';
  for (let i = lo; i <= hi; i++) s += m.tape.get(i) || '_';
  return s;
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const W = 11;
const MID = 5;
const NAMES = { inc: "Adds 1 to the binary number 1011. The head starts on the last bit; each 1 flips to 0 and carries left until a 0 or a blank becomes 1.", bb3: "A 3-state busy beaver on a blank tape. It halts after exactly 21 steps with five 1s, the most steps any halting 3-state, 2-symbol machine takes.", bb4: "A 4-state busy beaver: 107 steps and thirteen 1s, the record for 4 states. With a budget of 100 it looks like it may never stop, 7 steps short of halting.", add: "Unary addition 3 + 2: the blank between 111 and 11 is filled with a 1, then the final 1 is erased, leaving five 1s.", loop: "A binary counter that counts 1, 2, 3, and so on without end. It never halts, yet waiting can never prove that." };
let key = 'inc';
let m = makeMachine(key);
let timer = null;
const $ = (id) => document.getElementById(id);

function budget() { return parseInt($('budget').value, 10); }

function renderRules() {
  const p = m.p;
  const syms = p.symbols;
  let h = '<tr><th></th>' + syms.map((s) => '<th><span class="tok t' + s + '">' + (s === '_' ? '' : s) + '</span></th>').join('') + '</tr>';
  for (const st of p.states) {
    h += '<tr><th>' + st + '</th>';
    for (const s of syms) {
      const r = p.rules[st][s];
      h += '<td data-s="' + st + s + '">' + (r ? (r[0] === '_' ? '·' : r[0]) + ' ' + r[1] + ' ' + r[2] : '—') + '</td>';
    }
    h += '</tr>';
  }
  $('rules').innerHTML = h;
}

function markRule() {
  const cells = $('rules').querySelectorAll('td');
  const sym = m.tape.get(m.pos) || '_';
  cells.forEach((c) => c.classList.toggle('on', !m.halted && c.dataset.s === m.state + sym));
}

function renderTape() {
  let h = '';
  for (let i = 0; i < W; i++) {
    const idx = m.pos - MID + i;
    const s = m.tape.get(idx) || '_';
    h += '<div class="cell' + (i === MID ? ' here' : '') + '"><span class="tok t' + s + '">' + (s === '_' ? '' : s) + '</span></div>';
  }
  $('tape').innerHTML = h;
  const hr = $('headrow');
  hr.innerHTML = '';
  const mk = document.createElement('div');
  mk.className = 'marker' + (m.halted ? ' stop' : '');
  mk.textContent = m.halted ? 'H' : m.state;
  mk.style.gridColumn = String(MID + 1);
  hr.appendChild(mk);
}

function renderStats() {
  $('s_steps').textContent = m.steps;
  $('s_state').textContent = m.halted ? 'H' : m.state;
  $('s_ones').textContent = countOnes(m);
}

function verdict(kind) {
  const v = $('verdict');
  if (kind === 'halt') {
    v.className = 'verdict ok';
    v.textContent = i18nFmt("Halted after %n% steps with %k% ones on the tape.", { n: m.steps, k: countOnes(m) });
  } else if (kind === 'budget') {
    v.className = 'verdict warn';
    v.textContent = i18nFmt("Still running after %n% steps (budget reached). It may halt later or never; no algorithm decides this for every machine.", { n: m.steps });
  } else {
    v.className = 'verdict';
    v.textContent = "Press Step or Run. The machine will either halt or keep going.";
  }
}

function paint() {
  renderTape();
  renderStats();
  markRule();
  if (m.halted) verdict('halt');
}

function stop() {
  if (timer) { clearInterval(timer); timer = null; }
  $('run').textContent = "Run";
}

function load(k) {
  stop();
  key = k;
  m = makeMachine(k);
  document.querySelectorAll('#presets button').forEach((b) => b.classList.toggle('active', b.dataset.p === k));
  $('desc').textContent = NAMES[k];
  renderRules();
  verdict('ready');
  paint();
}

function doStep() {
  if (m.halted) return;
  if (m.steps >= budget()) { verdict('budget'); return; }
  stepMachine(m);
  paint();
  if (!m.halted && m.steps >= budget()) { stop(); verdict('budget'); }
}

function runTo(limit) {
  while (!m.halted && m.steps < limit) stepMachine(m);
}

function toggleRun() {
  if (timer) { stop(); return; }
  if (m.halted) return;
  $('run').textContent = "Pause";
  timer = setInterval(() => {
    const chunk = 1 + Math.floor(m.steps / 30);
    runTo(Math.min(budget(), m.steps + chunk));
    paint();
    if (m.halted) stop();
    else if (m.steps >= budget()) { stop(); verdict('budget'); }
  }, 70);
}

function skip() {
  stop();
  runTo(budget());
  paint();
  if (!m.halted) verdict('budget');
}

document.querySelectorAll('#presets button').forEach((b) => b.addEventListener('click', () => load(b.dataset.p)));
$('step').addEventListener('click', () => { stop(); doStep(); });
$('run').addEventListener('click', toggleRun);
$('skip').addEventListener('click', skip);
$('reset').addEventListener('click', () => load(key));
$('budget').addEventListener('change', () => { if (!m.halted) verdict('ready'); });
load('inc');
Result
Console

Start with Binary +1 and press Step: the transition table highlights the rule being applied. Then try Busy beaver 3 and Busy beaver 4, which are champions in the busy beaver competition: they halt after 21 and 107 steps. Now lower the step budget to 100 and run Busy beaver 4 again. At step 100 it is still running, and nothing on the tape tells you it will stop seven steps later. Finally run Never halts, a binary counter that counts forever: whatever budget you choose, it is still running when the budget ends. The two verdicts look identical at the budget, and that ambiguity is the halting problem in miniature.

The Real Complexity

The embedding. The authors encode Yurii Rogozhin's small universal Turing machine with 2 states and 18 symbols, usually written UTM(2,18). Each symbol is a creature type. The tape is a line of creature tokens whose power and toughness record how far each cell is from the head, and whose color (green or white) says on which side of the head it lies. A few cards such as Rotlung Reanimator and Xathrid Necromancer create the next token when the right creature dies, which plays the role of the transition rule, and Infest kills the token under the head so that its type is "read". Phasing switches between the rule sets of the two machine states.

No choices. The key difficulty is that a game has two players who can make decisions, while a Turing machine is deterministic. In the paper every action of both players is forced: cards such as Wild Evocation force the one card the first player can cast each turn, and other cards remove the options to attack, spend mana or target the tape. With no real decision left, the game just runs the machine. If it halts, the first player wins through Coalition Victory; if it never halts, the game is a draw.

What follows.

  • Let HH be the set of machines that halt on blank input. The position built from MM is a first-player win if and only if M∈HM \in H, so "does the first player have a winning strategy?" is at least as hard as the halting problem. It is undecidable, but semi-decidable in this forced setting: you can confirm a halt by running the game, never a non-halt.
  • By Rice's theorem, any non-trivial property of what a machine computes is undecidable too, and the paper uses this to show that deciding whether two Magic strategies are equivalent is also undecidable.
  • In 2020 Stella Biderman extended the construction in Magic: the Gathering is as Hard as Arithmetic (arXiv 2003.05119). She shows that deciding whether a player can force a win within a given number of turns is hard at every level Δn0\Delta^0_n of the arithmetic hierarchy, so optimal play in Magic is not even arithmetic in general.
  • A much more modest result concerns a single move: Chatterjee and Ibsen-Jensen (2016) showed that checking whether a proposed set of blockers is legal in one step of the game is coNP-complete. Even a local question can be hard.
tape, pos, state = initial configuration
while state != HALT:
    (write, move, next) = rules[state][tape[pos]]
    tape[pos] = write
    pos = pos + (+1 if move == R else -1)
    state = next

This loop is all a Turing machine is, and the Magic construction implements it with creature tokens instead of an array. The loop may never exit, and no program can inspect the rule table in general and tell you whether it will.

A caveat. The result concerns the game as an abstract rule system with unbounded resources such as an arbitrarily long tape of tokens, and play that may continue indefinitely. Tournament time limits make any real match finite, and the paper does not claim that any actual match is undecidable. It says that no single algorithm can handle every legal position.

Where It Matters

Magic is one of a long list of accidentally Turing-complete systems, where enough interacting rules produce a universal computer that nobody designed:

  • Conway's Game of Life, a cellular automaton with two cell states and a few simple rules, can build logic gates and memory out of gliders and still lifes.
  • Rule 110, a one-dimensional cellular automaton whose universality was proved by Matthew Cook in a paper published in Complex Systems in 2004, after Stephen Wolfram conjectured it in 1985.
  • The x86 mov instruction: Stephen Dolan showed in 2013 that mov alone, plus one jump back to the start, can simulate a Turing machine.
  • PowerPoint: in 2017 Tom Wildenhain showed in a SIGBOVIK paper that slides with animations and triggers can run a Turing machine.

Why does it matter beyond trivia?

  • Verification. If a rule system is Turing complete, questions like "can this ever reach a bad state?" become undecidable in general. That is why the rules of file formats, templating languages and configuration systems are best kept deliberately weak.
  • Security. Unintended computation is the basis of weird machines: attackers chain existing features, such as image-format quirks or instructions already in memory, into a program the designers never intended.
  • Game design and AI. Game-playing AI relies on search. The Magic result shows that for sufficiently rich rule systems, no search, however clever, is complete, which helps explain why complex card games remain a hard test for AI.
  • Intuition about the limits of computation. It supports the Church–Turing thesis from the other side: universality is not rare or exotic, and it appears as soon as a system has unbounded memory and a way to branch on it.

Conclusion

By forcing every move, Churchill, Biderman and Herrick turned a game of Magic into a plain machine: tokens as tape, creature types as symbols, card triggers as transition rules. Everything that follows is inherited from the halting problem: no algorithm can always say who wins, and Biderman's later work pushes the difficulty up the arithmetic hierarchy.

The deeper lesson is about how little it takes. Cards written to make a game fun, with no thought of computation, turned out to be enough to contain a universal machine: the construction needs only a handful of them. The next time a system's rules seem too busy to analyze, remember that sometimes they cannot be analyzed in full, as with the busy beaver machines you just ran.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/magic-the-gathering-turing-complete/Content licensed under CC BY-NC 4.0.