Editing Post correspondence problem (section)

== Definition of the problem ==

Let <math>A</math> be an alphabet with at least two symbols.  The input of the problem consists of two finite lists <math>\alpha_{1}, \ldots, \alpha_{N}</math> and <math>\beta_{1}, \ldots, \beta_{N}</math> of words over <math>A</math>. A solution to this problem is a [[sequence]] of indices <math>(i_k)_{1 \le k \le K}</math> with <math>K \ge 1</math> and <math> 1 \le i_k \le N</math> for all <math>k</math>, such that

: <math>\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.</math>

The decision problem then is to decide whether such a solution exists or not.

===Alternative definition===

:<math>g: (i_1,\ldots,i_K) \mapsto \alpha_{i_1} \ldots \alpha_{i_K}</math>

:<math>h: (i_1,\ldots,i_K) \mapsto \beta_{i_1} \ldots \beta_{i_K}.</math>

This gives rise to an equivalent alternative definition often found in the literature, according to which any two homomorphisms <math>g,h</math> with a common domain and a common codomain form an instance of the Post correspondence problem, which now asks whether there exists a nonempty word <math>w</math> in the domain such that

:<math>g(w)=h(w)</math>.

Another definition describes this problem easily as a type of puzzle. We begin with a collection of dominos, each containing two strings, one on each side. An individual domino looks like 
:<math>\begin{bmatrix}a \\ ab\end{bmatrix} </math> 
and a collection of dominos looks like 
:<math>{ \begin{bmatrix}bc \\ ca\end{bmatrix}, \begin{bmatrix}a \\ ab\end{bmatrix}, \begin{bmatrix}ca \\ a\end{bmatrix}, \begin{bmatrix}abc \\ c\end{bmatrix} }</math>. 
The task is to make a list of these dominos (repetition permitted) so that the string we get by reading off the symbols on the top is the same as the string of symbols on the bottom. This list is called a  match. The Post correspondence problem is to determine whether a collection of dominos has a match.
For example, the following list is a match for this puzzle.
:<math>{ \begin{bmatrix}a \\ ab\end{bmatrix}, \begin{bmatrix}bc \\ ca\end{bmatrix}, \begin{bmatrix}a \\ ab\end{bmatrix}, \begin{bmatrix}abc \\ c\end{bmatrix} }</math>.
For some collections of dominos, finding a match may not be possible. For example, the collection
:<math>{ \begin{bmatrix}abc \\ ab\end{bmatrix}, \begin{bmatrix}ca \\ a\end{bmatrix}, \begin{bmatrix}acc \\ ba\end{bmatrix} }</math>.
cannot contain a match because every top string is longer than the corresponding bottom string.