Post correspondence problem


Let Σ be an alphabet. As usual, Σ+ denotes the set of all non-empty words over Σ. Let PΣ+×Σ+ be finite. Call a finite sequencePlanetmathPlanetmath

(u1,v1),,(un,vn)

of pairs in P a correspondence in P if

u1un=v1vn.

The word u1un is called a match in P.

For example, if Σ={a,b}, and P={(b,b2),(a2,a),(b2a,b3),(ab2,a2b)}. Then

(a2,a),(ab2,a2b),(b2a,b3),(ab2,a2b),(b,b2)

is a correspondence in P.

On the other hand, there are no correspondences in {(ab,a),(a,ba2)}.

The Post correspondence problem asks the following:

Is there an algorithmMathworldPlanetmath (Turing machineMathworldPlanetmath or any other equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath computing models) such that when an arbitrary P is given as an input, returns 1 if there exists a correspondence in P and 0 otherwise.

The problem is named after E. Post because he proved

Theorem 1.

The Post correspondence problem is unsolvable (no such algorithms exist).

Title Post correspondence problem
Canonical name PostCorrespondenceProblem
Date of creation 2013-03-22 19:09:59
Last modified on 2013-03-22 19:09:59
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Definition
Classification msc 68Q45