Post's correspondence problem

Post's correspondence problem
Name	Post's correspondence problem
Field	Theoretical computer science
Introduced	1946
Introduced by	Emil Post
Decidability	Undecidable
Related	Turing machine, Hilbert's tenth problem, Word problem for groups, Minsky machine

Post's correspondence problem

Post's correspondence problem is a decision problem in Mathematical logic and Theoretical computer science introduced by Emil Post. It asks whether, given a finite set of pairs of finite strings over a fixed alphabet, there exists a non-empty sequence of indices producing equal concatenations from the two coordinate sequences. The problem is notable for being one of the earliest natural undecidable problems and for its central role in reductions connecting diverse problems in Computability theory and Formal language theory.

Definition

Given a finite set of tiles each consisting of an ordered pair of non-empty words over a finite alphabet, the problem asks if there exists a finite sequence of tile indices i1,i2,...,ik (k ≥ 1) such that concatenating the first components in that order equals concatenating the second components. The input is a finite list of pairs, and the question is a yes/no decision about the existence of a matching sequence. Instances are often expressed in terms of words over alphabets linked to models like Turing machine encodings or Semi-Thue system presentations. The formulation connects to notions from Automata theory, Recursion theory, and constructions used in proofs about Undecidable problems.

Undecidability and Historical Context

Post formulated the problem in correspondence with contemporaries in the 1940s while developing work related to Hilbert's tenth problem and Decision problem (Entscheidungsproblem). Post proved undecidability by reductions leveraging constructions akin to those used by Alan Turing and Alonzo Church in establishing the unsolvability of the Entscheidungsproblem. The result sits alongside other seminal undecidable results such as the undecidability of the Word problem for groups by Pyotr Novikov and William Boone, and complements Matiyasevich’s theorem resolving Hilbert's tenth problem with connections to diophantine sets and Recursive function theory. Subsequent work by Martin Davis, Hilary Putnam, and Julia Robinson further clarified the landscape of natural undecidable problems, and researchers like Michael Rabin and Dana Scott explored related automata-theoretic consequences.

Variants and Restrictions

Numerous variants restrict alphabet size, tile counts, or allow additional operations. The problem remains undecidable for unary alphabets under certain encodings linked to Minsky machine simulations, while other restrictions yield decidability. For example, bounding tile multiplicity or enforcing monotone length constraints produces decidable fragments exploited in complexity analyses by scholars including Richard Karp and Jack Edmonds. Variants include the mortal matrix problem related to Matrix mortality problem, the Post embedding problem related to Higman embedding theorem, and constrained versions that connect to the Skolem problem. Complexity-theoretic studies relate restricted instances to classes like NP and PSPACE and draw comparisons with decision problems studied by Stephen Cook and Leonid Levin.

Proofs and Reductions

Proofs of undecidability employ reductions from canonical undecidable models. Classic reductions map computations of a Turing machine or configurations of a Minsky machine to matching sequences of tile indices, encoding state transitions and tape contents into word pairs. Constructions exploit encodings developed in the work of Emil Post, refined by later reductions using gadgets akin to those in reductions by Richard M. Karp, John Hopcroft, and Jeffrey Ullman. Alternative proofs reduce from the Word problem for semigroups and from undecidable tiling problems related to the Wang tile problem studied by Hao Wang. The toolkit includes the use of uniform morphisms, marker symbols inspired by Noam Chomsky’s formal grammars, and simulation techniques parallel to those used in proofs about Busy Beaver function uncomputability by Rado.

Applications and Consequences

Post’s correspondence problem serves as a central pivot for establishing undecidability across domains: formal language inclusion problems, reachability in models of computation, and verification questions in Model checking contexts originating in the work of Edmund Clarke and E. Allen Emerson. It underpins undecidability results for fixed-structure rewriting systems, constraints in string unification problems studied by researchers like Miller and Kapur, and hardness results for decision problems in Group theory and Semigroup theory explored by Graham Higman and John Conway. The problem’s reductions inform lower bounds and intractability proofs in Complexity theory and influence practical areas such as automated reasoning and static analysis approaches developed by teams at institutions like Bell Labs and IBM Research.

Examples and Instances

Concrete instances illustrate both solvable and unsolvable behavior. Small manually constructed sets of pairs demonstrate trivial solutions, while classic benchmark encodings used in proofs map specific Turing machine configurations to tile sets lacking matches, evidencing undecidability. Researchers have cataloged representative hard instances in collections circulated among groups studying Decidability and Formal verification; these instances are often derived from universal Turing machine encodings by authors like Marvin Minsky and others who developed universal small-state machines. Case studies include constructions showing undecidability persists under alphabet compression techniques related to work by Marek Karpinski and optimization of reductions by Christos Papadimitriou.

Category:Undecidable problems