ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck pass

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.

Using $A_{T M} \leq_{m}$ nonemptiness to transfer undecidability and recognizability information

Example

Let ${N O N E M P T Y}_{T M} : = {⌜ N ⌝ : L (N) \neq \emptyset} .$ The standard map from acceptance to nonemptiness shows how undecidability transfers along a many-one reduction.

Facts & Assumptions

Given: A coded pair $⟨ ⌜ M ⌝, \hat{w} ⟩$ .

[L1]

If $A \leq_{m} B$ , then decidability and recognizability of $B$ transfer backward to $A$ , by Computable many-one reductions transfer decidability and recognizability backward.

[L2]

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

Verification

technique · direct

1.1givenconstruct

From $⟨ ⌜ M ⌝, \hat{w} ⟩$ , build a machine $N_{M, w}$ that ignores its own input, simulates $M$ on $w$ , and accepts exactly when that simulation accepts. Then $L (N_{M, w}) \neq \emptyset$ exactly when $M$ accepts $w$ . So this construction gives a many-one reduction from $A_{T M}$ to ${N O N E M P T Y}_{T M}$ .

2.1L1L2step 1.1∎

If ${N O N E M P T Y}_{T M}$ were decidable, [L1] would make $A_{T M}$ decidable, contradicting [L2]. Thus the nonemptiness problem is undecidable. More generally, recognizability of a target pulls backward along a many-one reduction, while the contrapositive pushes nonrecognizability of the source forward to the target.

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

MIT 6.045J / 18.400J, Lecture 9: Mapping Reducibility and Rice's Theorem (standard reference, not scraped)

Using ATM≤mATM​≤m​ nonemptiness to transfer undecidability and recognizability information