The Entscheidungsproblem

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.

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">{{hint}}</p>

<div class="rack">
  <div class="card box">
    <div class="title">DECIDE(P)</div>
    <div class="sub">{{sub_decide}}</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">{{sub_spite}}</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">{{status_initial}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.

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.