False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

FALSE: undecidable means no individual instance can be answered

Statement

If a language is undecidable, then no specific instance of it can ever be answered correctly.

Facts & Assumptions

Given: The acceptance problem $A_{T M}$ .

[L1]

The language $A_{T M}$ is undecidable, by The Turing-machine acceptance problem is undecidable.

[L2]

A member of $A_{T M}$ is a coded machine/input pair on which the machine accepts the input, by The Turing-machine acceptance problem $A_{T M}$ .

Refutation

technique · direct

1.1

Let $M_{y e s}$ be the machine that immediately enters its accepting state on every input. Then, by [L2], the specific coded pair $⟨ ⌜ M_{y e s} ⌝, \hat{1} ⟩$ lies in $A_{T M}$ , and this yes-answer is completely explicit.

L2givenconstruct

2.1

Step 1.1 shows that at least one individual instance of $A_{T M}$ is easy to answer, while [L1] says the whole language is still undecidable. So undecidability cannot mean that every particular instance is beyond analysis; it means only that no single algorithm decides all instances.

L1step 1.1∎

Depends on

Used by

An immediate-accept machine gives an easy yes-instance inside an undecidable language 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

EECS 376 Course Notes, Part 6: Computability (standard reference, not scraped)