CounterexampleConstruction: AI-generatedVerification: 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.

A universal machine diverges on a looping machine/input pair

Statement refuted

The false statement FALSE: universality decides halting claims that every universal Turing machine decides whether the simulated machine halts.

Let $M_{l o o p} = (3, 0, 1, τ_{l o o p})$ be the coded machine with its unique transition given by $τ_{l o o p} (0, 0) = (0, 0, 1)$ . Since its input alphabet is empty, its unique input word is $ε$ . Fix any universal machine $U$ for the chosen coding, whose existence is guaranteed by A universal Turing machine exists for the chosen coding, and take the coded input $⟨ ⌜ M_{l o o p} ⌝, \hat{ε} ⟩$ .

Facts & Assumptions

Given: The looping machine $M_{l o o p}$ , a universal machine $U$ , and the coded input $⟨ ⌜ M_{l o o p} ⌝, \hat{ε} ⟩$ .

[L1]

The false statement being refuted says that universality itself yields a halting decider, by FALSE: universality decides halting.

[L2]

There exists a universal Turing machine for the chosen coding, by A universal Turing machine exists for the chosen coding.

Counterexample

technique · direct

1.1

The machine $M_{l o o p}$ has an infinite run on its unique input $ε$ , because its only action is to move right forever and it never enters a halting state.

given

2.1

By the universality clause recalled in the counterexample statement, the universal machine $U$ must reproduce that same infinite run on the coded input $⟨ ⌜ M_{l o o p} ⌝, \hat{ε} ⟩$ . So $U$ diverges on this input rather than halting with a yes-or-no answer.

givenstep 1.1

3.1

Therefore the coded input $⟨ ⌜ M_{l o o p} ⌝, \hat{ε} ⟩$ is a counterexample to the claim in [L1]. The existence assertion [L2] shows that this is a genuine instance in the chosen coding scheme.

L1L2step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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

A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (standard reference, not scraped)