Alphabeta Math
False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-09-12
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

FALSE: universality decides halting

Statement

False claim: every universal Turing machine decides, for each coded machine M and each input word w for M, whether M halts on input w.

Facts & Assumptions

Given: The false claim above.

[A1]

Every universal Turing machine decides, for each coded machine M and each input word w for M, whether M halts on input w.

[L1]

A universal machine must reproduce both the halting outputs and the divergence of every coded machine on every coded input, by A universal Turing machine relative to a fixed machine encoding.

[L2]

A machine diverges on an input exactly when there is no halting computation history on that input, by Finite computation histories, halting computations, and divergence.

[L3]

Universal Turing machines for the chosen coding exist, by A universal Turing machine exists for the chosen coding.

Refutation

technique · direct
1.1

Let Mloop=(3,0,1,τloop), where the unique transition is τloop(0,0)=(0,0,1). Its input alphabet is empty, so its unique input word is ε. On that input the machine keeps state 0 forever, moves right at every step, and never reaches a halting state. Hence it has no halting computation history on ε, so by [L2] it diverges on ε.

L2given
2.1

By [L3], there exists at least one universal machine U. By [L1], the run of U on the coded input Mloop,ε^ must reproduce the divergence from step 1.1. Hence U does not halt on that instance.

L1L3step 1.1
3.1

A machine that fails to halt on some instance does not decide a yes-or-no halting problem on all instances. Step 2.1 therefore contradicts the false claim [A1].

A1step 2.1

Depends on

Used by

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources