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: rejection is divergence

Statement

False claim: whenever a deterministic Turing machine rejects an input, it diverges on that input.

Facts & Assumptions

Given: The machine with states $q_{0}, q_{a c c}, q_{r e j}$ , input alphabet ${1}$ , tape alphabet ${1, ⊔}$ , and transition rule $δ (q_{0}, 1) = (q_{r e j}, 1, R) .$ Take input word $w = 1$ .

[A1]

The statement refuted is: rejection on an input means divergence on that input.

[L1]

A halting computation history may end in a rejecting configuration, and divergence means that no halting computation history exists, by Finite computation histories, halting computations, and divergence.

[L2]

A configuration is rejecting exactly when its state is the designated reject state $q_{r e j}$ , by Initial, accepting, and rejecting configurations.

Refutation

technique · direct

1.1

On input $w = 1$ , the initial configuration scans the symbol 1 in state $q_{0}$ . The displayed transition sends that configuration in one step to a configuration whose state is $q_{r e j}$ .

given

2.1

By [L2], the configuration reached in step 1.1 is rejecting. So the two-term history consisting of the initial configuration and that next configuration is a halting computation history.

L2step 1.1

3.1

By [L1], an input with a halting computation history does not diverge. Thus this machine rejects $w$ without diverging, contradicting [A1].

A1L1step 2.1∎

Depends on

Used by

Immediate rejection is a halting computation, not a divergence Counterexample

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

Richard Zach, Sets, Logic, Computation: An Open Introduction to Metalogic (standard reference, not scraped)