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.

Halting on every input is not recognizable

Statement

Let TOTTM:={M:M is a coded deterministic one-tape Turing machine and M halts on every input word over its own input alphabet}. Then TOTTM is not recognizable.

Facts & Assumptions

Given: The totality language TOTTM.

[L1]

The complement of HALTTM is not recognizable, by The complement of the halting problem is not recognizable.

[L2]

The chosen machine encoding is effective, so from a code M,w^ one can effectively build a new coded machine whose finite control contains M and w^, by A fixed effective binary encoding of deterministic one-tape Turing machines.

[L3]

Recognizability means acceptance by some deterministic Turing machine on exactly the language members, by Decidable and recognizable languages.

[L4]

HALTTM is the language of coded pairs on which the decoded machine halts on the decoded input, by The halting problem HALTTM.

Proof

technique · direct
1.1

Given an input z=M,w^ for the complement of HALTTM from [L4], effectively build a machine TM,w with input alphabet Σ1={1} as follows. On input x, the machine simulates M on w for exactly x steps. If the simulation has not halted by then, TM,w halts and accepts. If the simulation has halted within those x steps, then TM,w enters an infinite loop. This construction is effective by [L2].

L2L4givenconstruct
2.1

If M never halts on w, then every finite step-bounded simulation in step 1.1 remains nonhalting, so TM,w halts on every input x. Conversely, if M halts on w after exactly t steps, then for every input x with xt the machine TM,w detects that halting event during its first x simulated steps and therefore loops forever. Hence M,w^HALTTM    TM,wTOTTM.

L4step 1.1
3.1

Suppose for contradiction that TOTTM were recognizable. Then, on input z=M,w^, one could compute TM,w and run the assumed recognizer for TOTTM on that code. By step 2.1, this would recognize the complement of HALTTM, contradicting [L1]. Therefore TOTTM is not recognizable, by [L3].

assume-contraL1L3step 2.1contradictiondischarge-contradiction: a recognizer for totality would recognize nonhalting

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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