Introduction

In 1928 the great mathematician David Hilbert posed a deceptively simple challenge, the Entscheidungsproblem — German for "decision problem." Is there a single mechanical procedure that, given any statement in first-order logic, decides whether it is universally valid? Feed in a sentence, turn the crank, get back a definite yes or no.

If such a procedure existed, mathematics would, in a sense, be finished. Every conjecture — Goldbach, the Riemann Hypothesis, anything you could phrase — would become a calculation. Truth would be a matter of waiting for the machine.

Hilbert believed the answer would be yes. He was wrong. In 1936, independently, Alonzo Church and Alan Turing proved that no such algorithm can exist. The result is not "we haven't found it yet" — it is proven impossible, forever. And in proving it, Turing had to invent the very idea of a computer.

Build the Impossible Decider

Suppose someone hands you DECIDE, a perfect box: feed it any logical statement and it answers yes or no. Could it really exist? Let's test the dream by trying to use it — and watch it collapse.

<p class="hint">Suppose <b>DECIDE</b> exists: a box that reads any program and says whether it <b>HALTS</b> or <b>LOOPS</b> forever. Build the trap program <b>SPITE</b> with it, then run DECIDE on SPITE itself and watch the logic break.</p>

<div class="rack">
  <div class="card box">
    <div class="title">DECIDE(P)</div>
    <div class="sub">our assumed truth-machine</div>
    <code>if P halts &rarr; return HALTS<br>else &rarr; return LOOPS</code>
  </div>
  <div class="card spite">
    <div class="title">SPITE()</div>
    <div class="sub">deliberately contrary</div>
    <code>if DECIDE(SPITE)==HALTS:<br>&nbsp;&nbsp;loop forever<br>else:<br>&nbsp;&nbsp;halt</code>
  </div>
</div>

<div class="status" id="status">Click below to ask DECIDE about SPITE.</div>
<div class="btns">
  <button id="run" type="button">Run DECIDE(SPITE)</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="trace" id="trace"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.rack { display: flex; gap: .7rem; flex-wrap: wrap; margin: .4rem 0 .8rem; }
.card { flex: 1 1 200px; border-radius: 10px; padding: .7rem .8rem; border: 1px solid #cdd9e3; background: #f3f7fb; }
.card.spite { background: #fdeef0; border-color: #f3c9cf; }
.title { font: 700 15px ui-monospace, monospace; color: #1d3557; }
.card.spite .title { color: #c92f3c; }
.sub { font-size: .78rem; color: #667; margin: .1rem 0 .5rem; }
code { display: block; font: 600 12.5px ui-monospace, monospace; color: #2b3a4a; line-height: 1.5; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.trace { font: 500 13px ui-monospace, monospace; color: #333; line-height: 1.6; }
.trace .step { padding: .2rem 0; opacity: 0; transform: translateY(4px); transition: all .25s; }
.trace .step.show { opacity: 1; transform: none; }
.trace .clash { color: #c92f3c; font-weight: 700; }
.trace .arrow { color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The Entscheidungsproblem reduces to the halting problem. A universal decider
    // DECIDE(P) would let us build SPITE: it asks DECIDE about ITSELF and then does
    // the OPPOSITE. Whatever DECIDE answers, SPITE makes it wrong — so DECIDE cannot
    // exist. This is Turing's 1936 diagonal contradiction, the core of the proof.

// We model both branches of DECIDE’s answer and show each leads to a clash.
function reason(answer){
  // answer is what DECIDE supposedly says about SPITE: ’HALTS’ or ’LOOPS’.
  // SPITE is built to do the opposite of DECIDE’s verdict.
  const spiteActuallyDoes = (answer === 'HALTS') ? 'LOOPS' : 'HALTS';
  const consistent = (spiteActuallyDoes === answer); // can never be true
  return { answer, spiteActuallyDoes, consistent };
}

const steps = [
  a => fmt('DECIDE(SPITE) is forced to answer something: say it returns <b>%answer%</b>.', { answer: a.answer }),
  a => fmt('<span class="arrow">&rarr;</span> By DECIDE’s promise, that means SPITE truly %v%.', { v: a.answer === 'HALTS' ? 'halts' : 'loops forever' }),
  a => fmt('<span class="arrow">&rarr;</span> But SPITE was written to do the OPPOSITE of DECIDE: so SPITE actually <b>%spiteActuallyDoes%</b>.', { spiteActuallyDoes: a.spiteActuallyDoes }),
  a => fmt('<span class="clash">&#10007; Contradiction: DECIDE said %answer%, SPITE does %spiteActuallyDoes%.</span>', { answer: a.answer, spiteActuallyDoes: a.spiteActuallyDoes })
];

let toggle = 'HALTS';

function run(){
  const a = reason(toggle);
  toggle = (toggle === 'HALTS') ? 'LOOPS' : 'HALTS'; // try the other branch next time
  const t = document.getElementById('trace'); t.innerHTML = '';
  const s = document.getElementById('status');
  s.textContent = 'Tracing the logic...'; s.className = 'status';
  steps.forEach((fn,i) => {
    const d = document.createElement('div'); d.className = 'step'; d.innerHTML = fn(a);
    t.appendChild(d);
    setTimeout(() => d.classList.add('show'), 250 * (i+1));
  });
  setTimeout(() => {
    s.textContent = 'No consistent answer exists — so DECIDE cannot exist. (Try again; the other branch fails too.)';
    s.className = 'status bad';
  }, 250 * (steps.length+1));
  console.assert(!a.consistent, 'DECIDE must be inconsistent for SPITE');
  console.log('Branch', a.answer, '-> SPITE does', a.spiteActuallyDoes, '| consistent?', a.consistent);
}
function reset(){
  document.getElementById('trace').innerHTML = '';
  const s = document.getElementById('status');
  s.textContent = 'Click below to ask DECIDE about SPITE.'; s.className = 'status';
  toggle = 'HALTS';
}
document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', reset);
Result
Console

The demo wires the dream to the halting problem: "will program P stop, or run forever?" Turing showed that question is undecidable. But if DECIDE existed, we could phrase "P halts on input X" as a logical statement and just ask it. That would solve the halting problem — which is impossible. So DECIDE cannot exist. The same loop that breaks the box is the heart of Turing's 1936 proof.

The Real Status

Where does the Entscheidungsproblem stand today? It is settled — and settled negatively.

  • Status: proven undecidable (1936). Alonzo Church (using his lambda calculus) and Alan Turing (using his machines) each proved, independently and in the same year, that no algorithm decides validity in first-order logic.
  • It is not "open." Unlike the Riemann Hypothesis or P vs NP, this is not a question awaiting an answer. The answer is in, and it is no — impossible.
  • The method was the reduction. Turing built a precise model of computation (the Turing machine), proved the halting problem has no decider, then showed that a decider for logic would yield a decider for halting. One impossibility forces the other.
  • It created a new field. To even state "no algorithm exists," Turing first had to define "algorithm." That definition — the Turing machine — is the foundation of all of computer science.

The deep lesson is the existence of undecidable problems: questions that are perfectly well-defined yet beyond any possible mechanical procedure. The Entscheidungsproblem was the first, and it sits next to the halting problem at the bedrock of the limits of computation.

Where It Matters

A 90-year-old impossibility proof might sound abstract, yet it quietly bounds what every piece of software can ever do:

  • No perfect bug finder. Because halting is undecidable, no tool can decide in general whether your code loops forever, crashes, or is correct. Analyzers must approximate, and sometimes guess.
  • Automated theorem proving. Provers like Coq, Lean and Isabelle are powerful but can never be complete deciders for all of mathematics — the Entscheidungsproblem says so.
  • Decidable islands. The negative result pushed researchers to find logics that are decidable (Presburger arithmetic, many description logics). Those islands power databases, type checkers and verification tools.
  • The Church–Turing thesis. Defining "algorithm" so precisely gave us a single notion of computation shared by every programming language and every machine.

The same wall appears in cousins like the halting problem and program equivalence — all heirs of the question Hilbert asked and Turing answered.

Conclusion

Hilbert asked for a machine that could decide all of mathematics. Turing and Church answered, in 1936, that no such machine can ever be built — not for lack of cleverness, but as a law of logic itself. Some perfectly meaningful questions simply have no algorithm.

It is one of history's great ironies: in proving that the universal decider is impossible, Turing had to dream up the universal computer. The "no" to Hilbert's dream is the "yes" that started ours. Every device you own is a child of a question that ended in defeat.

From here the story flows straight into the halting problem and the wider map of P vs NP — the difference between what is hard and what is flatly impossible.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/entscheidungsproblem/Content licensed under CC BY-NC 4.0.