Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-02
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.

The halting problem is recognizable and undecidable

Statement

The language HALTTM of The halting problem HALTTM is recognizable but not decidable.

Facts & Assumptions

Given: The halting language HALTTM.

[L1]

A binary word lies in HALTTM exactly when it has the form M,w^ and the decoded machine M halts on the decoded input word w, by The halting problem HALTTM.

[L2]

The chosen machine encoding has a total decoder that either reconstructs the unique coded machine or reports malformed input, by A fixed effective binary encoding of deterministic one-tape Turing machines.

[L3]

There is a deterministic one-tape interpreter that, from a valid pair consisting of a machine code and a configuration code, returns the same configuration code in the halting case and the unique one-step successor in the nonhalting case, by A fixed interpreter can execute one encoded machine step.

[L4]

The well-formed machine-description language is decidable, by Well-formed deterministic one-tape Turing machine descriptions form a decidable language.

[L5]

A language is recognizable when some deterministic Turing machine accepts exactly its members, and it is decidable when such a machine also halts on every input, by Decidable and recognizable languages.

[L6]

A machine either halts on an input by reaching an accepting or rejecting configuration, or else diverges on that input, by Finite computation histories, halting computations, and divergence.

[L7]

The acceptance language ATM is undecidable, by The Turing-machine acceptance problem is undecidable.

Proof

technique · direct
1.1

Recognizability: build a deterministic one-tape machine R that, on input z, first parses z as a candidate pair x,y. If the pair parse fails, it rejects. It next runs the decider from [L4] on x; if x is not a well-formed machine code, it rejects. If x is valid, it uses [L2] to recover the coded machine M=(m,s,n,τ). It then parses y as a candidate word code c(bin())c(bin(a1))c(bin(a)), rejects if that parse fails, and also rejects if some recovered symbol ai lies outside the input alphabet Σs={1,,s}. From the recovered word w=a1a, the machine writes the canonical initial configuration code of M on input w.

L1L2L4givenconstruct
1.2

Undecidability: if HALTTM were decidable, then by [L5] there would be a deterministic decider K for HALTTM. Given an input M,w^ for ATM, effectively build a machine NM,w that ignores its own input, simulates M on w, halts and accepts if that simulation accepts, and otherwise loops forever. Then M,w^ATM    NM,w,ε^HALTTM. Indeed, NM,w halts on the blank input exactly in the case that M accepts w. So the assumed decider K would decide ATM, which [L7] forbids.

L5L7givenconstruct
2.1

The machine R now repeatedly invokes the one-step interpreter from [L3] on the pair consisting of the recovered code x=M and the current configuration code. After each return, it reads the decoded state component of that configuration code. If the state is accepting or rejecting, R accepts. Otherwise it feeds the returned successor configuration back into the next interpreter call.

L3step 1.1construct
3.1

By [L3], each iteration in step 2.1 maintains exactly the current configuration of M on w. Therefore R accepts precisely when M eventually reaches an accepting or rejecting configuration on w, and diverges when M diverges. By [L1], [L5], and [L6], this means that R recognizes HALTTM.

L1L3L5L6step 2.1
4.1

Steps 3.1 and 1.2 prove recognizability and undecidability, respectively. Therefore HALTTM is recognizable and undecidable.

step 3.1step 1.2

Depends on

Used by

Dependency tree · two levels

18 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