DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 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.

The Post correspondence problem

Definition

Fix a finite alphabet $Σ$ . A Post correspondence problem instance over $Σ$ is a finite list of pairs of nonempty words $(u_{1}, v_{1}), \dots, (u_{n}, v_{n}) \in (Σ^{+} \times Σ^{+}) .$

A match for that instance is a nonempty finite index sequence $i_{1}, \dots, i_{k} \in {1, \dots, n}$ such that $u_{i_{1}} \dots u_{i_{k}} = v_{i_{1}} \dots v_{i_{k}} .$

The Post correspondence problem asks, given such a finite list of dominoes, whether a match exists.

Remarks

The chosen sequence may repeat dominoes.
The equality compares the two concatenated words exactly as written. One may choose dominoes and their order, but one may not reorder symbols inside a domino.

Used by

The modified Post correspondence problem Definition
FALSE: PCP permits reordering symbols inside a domino False statement
Modified PCP many-one reduces to PCP Lemma
The Post correspondence problem is recognizable Proposition
CFG ambiguity is undecidable Theorem
Emptiness of the intersection of two CFGs is undecidable Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

John Watrous, Introduction to the Theory of Computing (standard reference, not scraped)
MIT OpenCourseWare, Lecture 10: Computation History Method (standard reference, not scraped)