Namespaces
Variants
Actions

Difference between revisions of "Post correspondence problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (fix)
m (ce)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
p0740201.png
 +
$#A+1 = 192 n = 0
 +
$#C+1 = 192 : ~/encyclopedia/old_files/data/P074/P.0704020 Post correspondence problem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
This is one of the three basic undecidable problems, the other two being the halting problem and Hilbert's tenth problem. To establish the algorithmic unsolvability of a specific problem, a reduction to the Post correspondence problem, [[#References|[a3]]], is in many cases the most natural procedure.
 
This is one of the three basic undecidable problems, the other two being the halting problem and Hilbert's tenth problem. To establish the algorithmic unsolvability of a specific problem, a reduction to the Post correspondence problem, [[#References|[a3]]], is in many cases the most natural procedure.
  
 
Proofs of [[Undecidability|undecidability]] are either direct or indirect. Indirect proofs require some points of reference: problems already known to be undecidable. In regard to language theory, the most useful among such points of reference is the Post correspondence problem. For instance, when dealing with context-free languages, it is rather difficult to use the halting problem as a point of reference, whereas the Post correspondence problem is very suitable.
 
Proofs of [[Undecidability|undecidability]] are either direct or indirect. Indirect proofs require some points of reference: problems already known to be undecidable. In regard to language theory, the most useful among such points of reference is the Post correspondence problem. For instance, when dealing with context-free languages, it is rather difficult to use the halting problem as a point of reference, whereas the Post correspondence problem is very suitable.
  
The Post correspondence problem can be described as follows. One has to decide for two lists, both consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740201.png" /> words, whether or not some catenation of words in one list equals the corresponding catenation of words in the other list. Here  "corresponding"  means that words in exactly the same positions in the two lists must be used. For example, if the two lists are
+
The Post correspondence problem can be described as follows. One has to decide for two lists, both consisting of $  n $
 +
words, whether or not some catenation of words in one list equals the corresponding catenation of words in the other list. Here  "corresponding"  means that words in exactly the same positions in the two lists must be used. For example, if the two lists are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740202.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$ \tag{a1 }
 +
( a  ^ {2} , b  ^ {2} , ab  ^ {2} ) \  \textrm{ and } \ \
 +
( a  ^ {2} b , ba , b )
 +
$$
  
and one catenates the first, second, first, and third words in the lists (in this order), then the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740203.png" /> results in both cases. This is expressed by saying that  "the sequence of indices 1, 2, 1, 3 is a solution for an instance of the Post correspondence problemsolution for instance of the Post correspondence problem" . On the other hand, the instance consisting of the two lists
+
and one catenates the first, second, first, and third words in the lists (in this order), then the word $  a  ^ {2} b  ^ {2} a  ^ {3} b  ^ {2} $
 +
results in both cases. This is expressed by saying that  "the sequence of indices 1, 2, 1, 3 is a solution for an instance of the Post correspondence problem" . On the other hand, the instance consisting of the two lists
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740204.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
$$ \tag{a2 }
 +
( a  ^ {2} b , a ) \  \textrm{ and } \  ( a  ^ {2} , ba  ^ {2} )
 +
$$
  
possesses no solution. This can be shown by the following argument. A possible solution of (a2) must begin with the index 1. Then the index 2 must follow, because the word coming from the second list must  "catch up"  the missing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740205.png" />. So far the words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740206.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740207.png" /> are obtained. Since one of the words must always be a prefix of the other, one concludes that the next index in the solution must be 2, yielding the words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740208.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p0740209.png" />. But because neither of the words in the first list begins with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402010.png" />, one concludes that no further continuation is possible.
+
possesses no solution. This can be shown by the following argument. A possible solution of (a2) must begin with the index 1. Then the index 2 must follow, because the word coming from the second list must  "catch up"  the missing $  b $.  
 +
So far the words $  a  ^ {2} ba $
 +
and $  a  ^ {2} ba  ^ {2} $
 +
are obtained. Since one of the words must always be a prefix of the other, one concludes that the next index in the solution must be 2, yielding the words $  a  ^ {2} ba  ^ {2} $
 +
and $  a  ^ {2} ba  ^ {2} ba  ^ {2} $.  
 +
But because neither of the words in the first list begins with $  b $,  
 +
one concludes that no further continuation is possible.
  
The notion of a morphism provides a convenient way of giving a formal definition for the Post correspondence problem. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402012.png" /> be two morphisms with domain alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402013.png" /> and range alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402014.png" />. The pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402015.png" /> is called an instance of the Post correspondence problem. A non-empty word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402016.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402017.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402018.png" /> is referred to as a solution of this instance.
+
The notion of a morphism provides a convenient way of giving a formal definition for the Post correspondence problem. Let $  g $
 +
and $  h $
 +
be two morphisms with domain alphabet $  \Sigma $
 +
and range alphabet $  \Delta $.  
 +
The pair $  ( g, h ) $
 +
is called an instance of the Post correspondence problem. A non-empty word $  w $
 +
over $  \Sigma $
 +
such that $  g( w) = h( w) $
 +
is referred to as a solution of this instance.
  
For some instances of the Post correspondence problem it is rather easy to find out whether or not they have solutions. Above it was observed that (a1) has a solution, whereas (a2) has no solution. There are also some classes of instances for which an easy decision procedure exists. One such class consists of all instances for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402019.png" /> consists of a single letter. Then the two lists have the form
+
For some instances of the Post correspondence problem it is rather easy to find out whether or not they have solutions. Above it was observed that (a1) has a solution, whereas (a2) has no solution. There are also some classes of instances for which an easy decision procedure exists. One such class consists of all instances for which $  \Delta $
 +
consists of a single letter. Then the two lists have the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
$$ \tag{a3 }
 +
( a ^ {i _ {1} } \dots a ^ {i _ {n} } ) \  \textrm{ and } \ \
 +
( a ^ {j _ {1} } \dots a ^ {j _ {n} } ) .
 +
$$
  
It is easy to verify that (a3) has a solution if and only if either there is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402021.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402022.png" />, or else there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402024.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402026.png" />.
+
It is easy to verify that (a3) has a solution if and only if either there is a $  t $
 +
such that $  i _ {t} = j _ {t} $,  
 +
or else there are $  t $
 +
and $  u $
 +
such that $  i _ {t} > j _ {t} $
 +
and $  i _ {u} < j _ {u} $.
  
 
By the decidability of the Post correspondence problem is meant the existence of an algorithm that settles every instance. To show the undecidability of the Post correspondence problem, one reduces it to the halting problem, or, equivalently, to the membership problem of recursively enumerable languages. (See [[Formal languages and automata|Formal languages and automata]].)
 
By the decidability of the Post correspondence problem is meant the existence of an algorithm that settles every instance. To show the undecidability of the Post correspondence problem, one reduces it to the halting problem, or, equivalently, to the membership problem of recursively enumerable languages. (See [[Formal languages and automata|Formal languages and automata]].)
  
Assume that the Post correspondence problem is decidable and consider an arbitrary grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402027.png" /> with non-terminal and terminal alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402029.png" />, respectively, start letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402030.png" />, and set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402031.png" /> of productions. Further, consider an arbitrary word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402032.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402033.png" />. Below an instance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402034.png" /> of the Post correspondence problem is constructed such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402035.png" /> has a solution if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402036.png" /> is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402037.png" />. Since the construction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402038.png" /> will be effective, this gives a method of deciding whether or not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402039.png" /> is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402040.png" />.
+
Assume that the Post correspondence problem is decidable and consider an arbitrary grammar $  G $
 +
with non-terminal and terminal alphabets $  \Sigma _ {N} $
 +
and $  \Sigma _ {T} $,  
 +
respectively, start letter $  S $,  
 +
and set $  P $
 +
of productions. Further, consider an arbitrary word $  w $
 +
over $  \Sigma _ {T} $.  
 +
Below an instance $  PCP $
 +
of the Post correspondence problem is constructed such that $  PCP $
 +
has a solution if and only if $  w $
 +
is in $  L( G) $.  
 +
Since the construction of $  PCP $
 +
will be effective, this gives a method of deciding whether or not $  w $
 +
is in $  L( G) $.
  
The letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402041.png" /> are denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402042.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402043.png" /> is the start letter. Let
+
The letters of $  \Sigma _ {N} \cup \Sigma _ {T} = \Sigma _ {1} $
 +
are denoted by $  a _ {1} \dots a _ {r} $,  
 +
where $  a _ {1} $
 +
is the start letter. Let
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402044.png" /></td> </tr></table>
+
$$
 +
\{ {\alpha _ {i} \rightarrow \beta _ {i} } : {1 \leq  i \leq  n } \}
 +
$$
  
be the set of productions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402045.png" />. It may be assumed that none of the words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402047.png" /> is empty. Let
+
be the set of productions of $  G $.  
 +
It may be assumed that none of the words $  \alpha _ {i} $
 +
and $  \beta _ {i} $
 +
is empty. Let
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402048.png" /></td> </tr></table>
+
$$
 +
\Sigma _ {1}  ^  \prime  = \{ {a  ^  \prime  } : {a \in \Sigma _ {1} } \}
 +
,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402049.png" /></td> </tr></table>
+
$$
 +
\Delta  = \Sigma _ {1} \cup \Sigma _ {1}  ^  \prime  \cup
 +
\{ B, E, \# , \#  ^  \prime  \} .
 +
$$
  
(It is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402052.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402053.png" /> are letters not contained in the other alphabets considered. Intuitively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402054.png" /> marks the beginning of a derivation and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402055.png" /> the end of it, whereas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402057.png" /> are markers between two consecutive words in a derivation.) For any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402058.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402059.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402060.png" /> denote the word over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402061.png" /> obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402062.png" /> by replacing every letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402063.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402064.png" />.
+
(It is assumed that $  B $,  
 +
$  E $,  
 +
$  \# $,  
 +
and $  \#  ^  \prime  $
 +
are letters not contained in the other alphabets considered. Intuitively, $  B $
 +
marks the beginning of a derivation and $  E $
 +
the end of it, whereas $  \# $
 +
and $  \#  ^  \prime  $
 +
are markers between two consecutive words in a derivation.) For any word $  x $
 +
over $  \Sigma _ {1} $,  
 +
let $  x  ^  \prime  $
 +
denote the word over $  \Sigma _ {1}  ^  \prime  $
 +
obtained from $  x $
 +
by replacing every letter $  a _ {i} $
 +
with $  a _ {i}  ^  \prime  $.
  
Consider the instance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402065.png" /> of the Post correspondence problem. The domain alphabet of the morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402067.png" /> is
+
Consider the instance $  PCP=( g, h) $
 +
of the Post correspondence problem. The domain alphabet of the morphisms $  g $
 +
and $  h $
 +
is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402068.png" /></td> </tr></table>
+
$$
 +
\Sigma  = \{ 1 \dots 2r+ 2n+ 4 \} ,
 +
$$
  
and the range alphabet is the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402069.png" /> defined above. The morphisms themselves are defined by the following table, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402070.png" /> ranges over the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402071.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402072.png" /> ranges over the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402073.png" />.
+
and the range alphabet is the alphabet $  \Delta $
 +
defined above. The morphisms themselves are defined by the following table, where $  i $
 +
ranges over the numbers $  1 \dots r $
 +
and $  j $
 +
ranges over the numbers $  1 \dots n $.
  
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402074.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402075.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402076.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402077.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402078.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402079.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402080.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402081.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402082.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402083.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402084.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402085.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402086.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402087.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402088.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402089.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402090.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402091.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402092.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402093.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402094.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402095.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402096.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402097.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402098.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p07402099.png" /></td> </tr> </tbody> </table>
+
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"> $  1 $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  2 $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  3 $
 +
</td> <td colname="5" style="background-color:white;" colspan="1"> $  4 $
 +
</td> <td colname="6" style="background-color:white;" colspan="1"> $  4+ i $
 +
</td> <td colname="7" style="background-color:white;" colspan="1"> $  4+ r+ i $
 +
</td> <td colname="8" style="background-color:white;" colspan="1"> $  4+ 2r+ j $
 +
</td> <td colname="9" style="background-color:white;" colspan="1"> $  4+ 2r+ n+ j $
 +
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  g $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"> $  Ba _ {1} \# $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  \#  ^  \prime  $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  \# $
 +
</td> <td colname="5" style="background-color:white;" colspan="1"> $  E $
 +
</td> <td colname="6" style="background-color:white;" colspan="1"> $  a _ {i}  ^  \prime  $
 +
</td> <td colname="7" style="background-color:white;" colspan="1"> $  a _ {i} $
 +
</td> <td colname="8" style="background-color:white;" colspan="1"> $  \beta _ {j}  ^  \prime  $
 +
</td> <td colname="9" style="background-color:white;" colspan="1"> $  \beta _ {j} $
 +
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  h $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"> $  B $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  \# $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  \#  ^  \prime  $
 +
</td> <td colname="5" style="background-color:white;" colspan="1"> $  \#  ^  \prime  wE $
 +
</td> <td colname="6" style="background-color:white;" colspan="1"> $  a _ {i} $
 +
</td> <td colname="7" style="background-color:white;" colspan="1"> $  a _ {i}  ^  \prime  $
 +
</td> <td colname="8" style="background-color:white;" colspan="1"> $  \alpha _ {j} $
 +
</td> <td colname="9" style="background-color:white;" colspan="1"> $  \alpha _ {j}  ^  \prime  $
 +
</td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
  
Now <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020100.png" /> possesses a solution if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020101.png" />. Hence, if the Post correspondence problem is decidable, then so is the membership problem for recursively enumerable languages.
+
Now $  PCP $
 +
possesses a solution if and only if $  w \in L( G) $.  
 +
Hence, if the Post correspondence problem is decidable, then so is the membership problem for recursively enumerable languages.
  
The idea behind the construction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020102.png" /> is that derivations according to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020103.png" /> will be simulated. Moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020104.png" /> produces the derivation faster than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020105.png" /> because it starts with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020106.png" />, whereas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020107.png" /> starts only with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020108.png" />. The morphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020109.png" /> can catch up at the end of the derivation (by the index 4) if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020110.png" /> is the last word of the derivation.
+
The idea behind the construction of $  PCP $
 +
is that derivations according to $  G $
 +
will be simulated. Moreover, $  g $
 +
produces the derivation faster than $  h $
 +
because it starts with $  Ba _ {1} \# $,  
 +
whereas $  h $
 +
starts only with $  B $.  
 +
The morphism $  h $
 +
can catch up at the end of the derivation (by the index 4) if and only if $  w $
 +
is the last word of the derivation.
  
For example, assume that the first three productions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020111.png" /> are (in this order)
+
For example, assume that the first three productions of $  G $
 +
are (in this order)
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020112.png" /></td> </tr></table>
+
$$
 +
S  \rightarrow  aCD,\ \
 +
CD  \rightarrow  D ,\ \
 +
D  \rightarrow  d .
 +
$$
  
Assume, further, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020113.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020114.png" /> are the second and third letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020115.png" />, respectively. (Recall that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020116.png" />.) Consider the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020117.png" />. Clearly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020118.png" /> has the following derivation:
+
Assume, further, that $  a $
 +
and $  D $
 +
are the second and third letter of $  \Sigma _ {1} $,  
 +
respectively. (Recall that $  S = a _ {1} $.)  
 +
Consider the word $  w = ad $.  
 +
Clearly, $  w $
 +
has the following derivation:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020119.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>
+
$$ \tag{a4 }
 +
S  \Rightarrow  aCD  \Rightarrow  aD  \Rightarrow  ad.
 +
$$
  
Then a solution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020120.png" /> is constructed according to the table below.
+
Then a solution for $  PCP $
 +
is constructed according to the table below.
  
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020121.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020122.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020123.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020124.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020125.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020126.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020127.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020128.png" /></td> <td colname="10" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020129.png" /></td> <td colname="11" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020130.png" /></td> <td colname="12" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020131.png" /></td> <td colname="13" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020132.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020133.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020134.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020135.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020136.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020137.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020138.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020139.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020140.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020141.png" /></td> <td colname="10" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020142.png" /></td> <td colname="11" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020143.png" /></td> <td colname="12" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020144.png" /></td> <td colname="13" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020145.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020146.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020147.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020148.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020149.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020150.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020151.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020152.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020153.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020154.png" /></td> <td colname="10" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020155.png" /></td> <td colname="11" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020156.png" /></td> <td colname="12" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020157.png" /></td> <td colname="13" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020158.png" /></td> </tr> </tbody> </table>
+
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"> $  1 $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  4+ 2r+ 1 $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  2 $
 +
</td> <td colname="5" style="background-color:white;" colspan="1"> $  4+ r+ 2 $
 +
</td> <td colname="6" style="background-color:white;" colspan="1"> $  4+ 2r+ n+ 2 $
 +
</td> <td colname="7" style="background-color:white;" colspan="1"> $  3 $
 +
</td> <td colname="8" style="background-color:white;" colspan="1"> $  4+ 2 $
 +
</td> <td colname="9" style="background-color:white;" colspan="1"> $  4+ 3 $
 +
</td> <td colname="10" style="background-color:white;" colspan="1"> $  2 $
 +
</td> <td colname="11" style="background-color:white;" colspan="1"> $  4+ r+ 2 $
 +
</td> <td colname="12" style="background-color:white;" colspan="1"> $  4+ 2r+ n+ 3 $
 +
</td> <td colname="13" style="background-color:white;" colspan="1"> $  4 $
 +
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  g $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"> $  BS\# $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  a  ^  \prime  C  ^  \prime  D  ^  \prime  $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  \#  ^  \prime  $
 +
</td> <td colname="5" style="background-color:white;" colspan="1"> $  a $
 +
</td> <td colname="6" style="background-color:white;" colspan="1"> $  D $
 +
</td> <td colname="7" style="background-color:white;" colspan="1"> $  \# $
 +
</td> <td colname="8" style="background-color:white;" colspan="1"> $  a  ^  \prime  $
 +
</td> <td colname="9" style="background-color:white;" colspan="1"> $  D  ^  \prime  $
 +
</td> <td colname="10" style="background-color:white;" colspan="1"> $  \#  ^  \prime  $
 +
</td> <td colname="11" style="background-color:white;" colspan="1"> $  a $
 +
</td> <td colname="12" style="background-color:white;" colspan="1"> $  d $
 +
</td> <td colname="13" style="background-color:white;" colspan="1"> $  E $
 +
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  h $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"> $  B $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  S $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  \# $
 +
</td> <td colname="5" style="background-color:white;" colspan="1"> $  a  ^  \prime  $
 +
</td> <td colname="6" style="background-color:white;" colspan="1"> $  C  ^  \prime  D  ^  \prime  $
 +
</td> <td colname="7" style="background-color:white;" colspan="1"> $  \#  ^  \prime  $
 +
</td> <td colname="8" style="background-color:white;" colspan="1"> $  a $
 +
</td> <td colname="9" style="background-color:white;" colspan="1"> $  D $
 +
</td> <td colname="10" style="background-color:white;" colspan="1"> $  \# $
 +
</td> <td colname="11" style="background-color:white;" colspan="1"> $  a  ^  \prime  $
 +
</td> <td colname="12" style="background-color:white;" colspan="1"> $  D  ^  \prime  $
 +
</td> <td colname="13" style="background-color:white;" colspan="1"> $  \#  ^  \prime  adE $
 +
</td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
Line 67: Line 248:
 
Hence the word
 
Hence the word
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020159.png" /></td> </tr></table>
+
$$
 +
1( 4+ 2r+ 1) 2( 4+ r+ 2)( 4+ 2r+ n+ 2)
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020160.png" /></td> </tr></table>
+
$$
 +
3( 4+ 2)( 4+ 3) 2( 4+ r+ 2)( 4+ 2r+ n+ 3) 4
 +
$$
  
(where parentheses have been added for clarity) is a solution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020161.png" />, the common value of the morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020162.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020163.png" /> being for this word:
+
(where parentheses have been added for clarity) is a solution for $  PCP $,  
 +
the common value of the morphisms $  g $
 +
and $  h $
 +
being for this word:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020164.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a5)</td></tr></table>
+
$$ \tag{a5 }
 +
BS \# a  ^  \prime  C  ^  \prime  D  ^  \prime  \#  ^  \prime  aD\# a  ^  \prime  D  ^  \prime  \#  ^  \prime  adE .
 +
$$
  
Clearly, (a5) results from (a4) after the following simple modifications. The boundary markers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020165.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020166.png" /> are added to the beginning and end; the sign <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020167.png" /> is replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020168.png" />; moreover, every second step is primed, as is every second marker <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020169.png" />; finally, an  "idle"  step (from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020170.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020171.png" />) is added in order to reach the non-primed word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020172.png" /> corresponding to the final index of (a4).
+
Clearly, (a5) results from (a4) after the following simple modifications. The boundary markers $  B $
 +
and $  E $
 +
are added to the beginning and end; the sign $  \Rightarrow $
 +
is replaced by $  \# $;  
 +
moreover, every second step is primed, as is every second marker $  \# $;  
 +
finally, an  "idle"  step (from $  aD $
 +
to $  a  ^  \prime  D  ^  \prime  $)  
 +
is added in order to reach the non-primed word $  ad $
 +
corresponding to the final index of (a4).
  
It is easily seen that an analogous argument is valid in general: whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020173.png" /> is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020174.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020175.png" /> has a solution (see [[#References|[a4]]], where this fact is established by a detailed inductive argument). It is somewhat more difficult to establish the converse — that is, to show that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020176.png" /> has a solution, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020177.png" /> is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020178.png" />, see [[#References|[a4]]].
+
It is easily seen that an analogous argument is valid in general: whenever $  w $
 +
is in $  L( G) $,  
 +
then $  PCP $
 +
has a solution (see [[#References|[a4]]], where this fact is established by a detailed inductive argument). It is somewhat more difficult to establish the converse — that is, to show that if $  PCP $
 +
has a solution, then $  w $
 +
is in $  L( G) $,  
 +
see [[#References|[a4]]].
  
Using a simple encoding it can be shown that the Post correspondence problem remains undecidable if the range alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020179.png" /> of the morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020180.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020181.png" /> consists of two letters only. The decidability in case the domain alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020182.png" /> consists of two letters was established in [[#References|[a1]]]. Another non-trivial decidable subclass, [[#References|[a2]]], consists of instances <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020183.png" /> where one of the morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020184.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020185.png" /> is periodic, that is, all of its values are powers of a single word. The Post correspondence problem remains undecidable if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020186.png" /> consists of 9 letters. The decidability status is open if the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020187.png" /> is a fixed number between 3 and 8 (inclusive).
+
Using a simple encoding it can be shown that the Post correspondence problem remains undecidable if the range alphabet $  \Delta $
 +
of the morphisms $  g $
 +
and $  h $
 +
consists of two letters only. The decidability in case the domain alphabet $  \Sigma $
 +
consists of two letters was established in [[#References|[a1]]]. Another non-trivial decidable subclass, [[#References|[a2]]], consists of instances $  ( g, h) $
 +
where one of the morphisms $  g $
 +
and $  h $
 +
is periodic, that is, all of its values are powers of a single word. The Post correspondence problem remains undecidable if $  \Sigma $
 +
consists of 9 letters. The decidability status is open if the cardinality of $  \Sigma $
 +
is a fixed number between 3 and 8 (inclusive).
  
The Post correspondence problem is closely linked with equality sets, which are important in the representation theory of formal languages. By definition, the equality set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020188.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020189.png" /> consists of all words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020190.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020191.png" />. Clearly, an instance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074020/p074020192.png" /> possesses a solution if and only if the equality set contains a non-empty word.
+
The Post correspondence problem is closely linked with equality sets, which are important in the representation theory of formal languages. By definition, the equality set of $  g $
 +
and $  h $
 +
consists of all words $  w $
 +
such that $  g( w) = h( w) $.  
 +
Clearly, an instance $  ( g, h) $
 +
possesses a solution if and only if the equality set contains a non-empty word.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Ehrenfeucht,  J. Karhumäki,  G. Rozenberg,  "The (generalized) Post corresponding problem with lists consisting of two words is decidable"  ''Theor. Comp. Sc.'' , '''21'''  (1982)  pp. 119–144</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Karhumäki,  I. Simon,  "A note on elementary homomorphisms and the regularity of equality sets"  ''EATCS Bull.'' , '''9'''  (1979)  pp. 16–24</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  E. Post,  "A variant of a recursively unsolvable problem"  ''Bull. Amer. Math. Soc.'' , '''52'''  (1946)  pp. 264–268</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Salomaa,  "Formal languages" , Acad. Press  (1987)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Ehrenfeucht,  J. Karhumäki,  G. Rozenberg,  "The (generalized) Post corresponding problem with lists consisting of two words is decidable"  ''Theor. Comp. Sc.'' , '''21'''  (1982)  pp. 119–144</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Karhumäki,  I. Simon,  "A note on elementary homomorphisms and the regularity of equality sets"  ''EATCS Bull.'' , '''9'''  (1979)  pp. 16–24</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  E. Post,  "A variant of a recursively unsolvable problem"  ''Bull. Amer. Math. Soc.'' , '''52'''  (1946)  pp. 264–268</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Salomaa,  "Formal languages" , Acad. Press  (1987)</TD></TR></table>

Latest revision as of 14:02, 24 December 2020


This is one of the three basic undecidable problems, the other two being the halting problem and Hilbert's tenth problem. To establish the algorithmic unsolvability of a specific problem, a reduction to the Post correspondence problem, [a3], is in many cases the most natural procedure.

Proofs of undecidability are either direct or indirect. Indirect proofs require some points of reference: problems already known to be undecidable. In regard to language theory, the most useful among such points of reference is the Post correspondence problem. For instance, when dealing with context-free languages, it is rather difficult to use the halting problem as a point of reference, whereas the Post correspondence problem is very suitable.

The Post correspondence problem can be described as follows. One has to decide for two lists, both consisting of $ n $ words, whether or not some catenation of words in one list equals the corresponding catenation of words in the other list. Here "corresponding" means that words in exactly the same positions in the two lists must be used. For example, if the two lists are

$$ \tag{a1 } ( a ^ {2} , b ^ {2} , ab ^ {2} ) \ \textrm{ and } \ \ ( a ^ {2} b , ba , b ) $$

and one catenates the first, second, first, and third words in the lists (in this order), then the word $ a ^ {2} b ^ {2} a ^ {3} b ^ {2} $ results in both cases. This is expressed by saying that "the sequence of indices 1, 2, 1, 3 is a solution for an instance of the Post correspondence problem" . On the other hand, the instance consisting of the two lists

$$ \tag{a2 } ( a ^ {2} b , a ) \ \textrm{ and } \ ( a ^ {2} , ba ^ {2} ) $$

possesses no solution. This can be shown by the following argument. A possible solution of (a2) must begin with the index 1. Then the index 2 must follow, because the word coming from the second list must "catch up" the missing $ b $. So far the words $ a ^ {2} ba $ and $ a ^ {2} ba ^ {2} $ are obtained. Since one of the words must always be a prefix of the other, one concludes that the next index in the solution must be 2, yielding the words $ a ^ {2} ba ^ {2} $ and $ a ^ {2} ba ^ {2} ba ^ {2} $. But because neither of the words in the first list begins with $ b $, one concludes that no further continuation is possible.

The notion of a morphism provides a convenient way of giving a formal definition for the Post correspondence problem. Let $ g $ and $ h $ be two morphisms with domain alphabet $ \Sigma $ and range alphabet $ \Delta $. The pair $ ( g, h ) $ is called an instance of the Post correspondence problem. A non-empty word $ w $ over $ \Sigma $ such that $ g( w) = h( w) $ is referred to as a solution of this instance.

For some instances of the Post correspondence problem it is rather easy to find out whether or not they have solutions. Above it was observed that (a1) has a solution, whereas (a2) has no solution. There are also some classes of instances for which an easy decision procedure exists. One such class consists of all instances for which $ \Delta $ consists of a single letter. Then the two lists have the form

$$ \tag{a3 } ( a ^ {i _ {1} } \dots a ^ {i _ {n} } ) \ \textrm{ and } \ \ ( a ^ {j _ {1} } \dots a ^ {j _ {n} } ) . $$

It is easy to verify that (a3) has a solution if and only if either there is a $ t $ such that $ i _ {t} = j _ {t} $, or else there are $ t $ and $ u $ such that $ i _ {t} > j _ {t} $ and $ i _ {u} < j _ {u} $.

By the decidability of the Post correspondence problem is meant the existence of an algorithm that settles every instance. To show the undecidability of the Post correspondence problem, one reduces it to the halting problem, or, equivalently, to the membership problem of recursively enumerable languages. (See Formal languages and automata.)

Assume that the Post correspondence problem is decidable and consider an arbitrary grammar $ G $ with non-terminal and terminal alphabets $ \Sigma _ {N} $ and $ \Sigma _ {T} $, respectively, start letter $ S $, and set $ P $ of productions. Further, consider an arbitrary word $ w $ over $ \Sigma _ {T} $. Below an instance $ PCP $ of the Post correspondence problem is constructed such that $ PCP $ has a solution if and only if $ w $ is in $ L( G) $. Since the construction of $ PCP $ will be effective, this gives a method of deciding whether or not $ w $ is in $ L( G) $.

The letters of $ \Sigma _ {N} \cup \Sigma _ {T} = \Sigma _ {1} $ are denoted by $ a _ {1} \dots a _ {r} $, where $ a _ {1} $ is the start letter. Let

$$ \{ {\alpha _ {i} \rightarrow \beta _ {i} } : {1 \leq i \leq n } \} $$

be the set of productions of $ G $. It may be assumed that none of the words $ \alpha _ {i} $ and $ \beta _ {i} $ is empty. Let

$$ \Sigma _ {1} ^ \prime = \{ {a ^ \prime } : {a \in \Sigma _ {1} } \} , $$

$$ \Delta = \Sigma _ {1} \cup \Sigma _ {1} ^ \prime \cup \{ B, E, \# , \# ^ \prime \} . $$

(It is assumed that $ B $, $ E $, $ \# $, and $ \# ^ \prime $ are letters not contained in the other alphabets considered. Intuitively, $ B $ marks the beginning of a derivation and $ E $ the end of it, whereas $ \# $ and $ \# ^ \prime $ are markers between two consecutive words in a derivation.) For any word $ x $ over $ \Sigma _ {1} $, let $ x ^ \prime $ denote the word over $ \Sigma _ {1} ^ \prime $ obtained from $ x $ by replacing every letter $ a _ {i} $ with $ a _ {i} ^ \prime $.

Consider the instance $ PCP=( g, h) $ of the Post correspondence problem. The domain alphabet of the morphisms $ g $ and $ h $ is

$$ \Sigma = \{ 1 \dots 2r+ 2n+ 4 \} , $$

and the range alphabet is the alphabet $ \Delta $ defined above. The morphisms themselves are defined by the following table, where $ i $ ranges over the numbers $ 1 \dots r $ and $ j $ ranges over the numbers $ 1 \dots n $.

<tbody> </tbody>
$ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 4+ i $ $ 4+ r+ i $ $ 4+ 2r+ j $ $ 4+ 2r+ n+ j $
$ g $ $ Ba _ {1} \# $ $ \# ^ \prime $ $ \# $ $ E $ $ a _ {i} ^ \prime $ $ a _ {i} $ $ \beta _ {j} ^ \prime $ $ \beta _ {j} $
$ h $ $ B $ $ \# $ $ \# ^ \prime $ $ \# ^ \prime wE $ $ a _ {i} $ $ a _ {i} ^ \prime $ $ \alpha _ {j} $ $ \alpha _ {j} ^ \prime $

Now $ PCP $ possesses a solution if and only if $ w \in L( G) $. Hence, if the Post correspondence problem is decidable, then so is the membership problem for recursively enumerable languages.

The idea behind the construction of $ PCP $ is that derivations according to $ G $ will be simulated. Moreover, $ g $ produces the derivation faster than $ h $ because it starts with $ Ba _ {1} \# $, whereas $ h $ starts only with $ B $. The morphism $ h $ can catch up at the end of the derivation (by the index 4) if and only if $ w $ is the last word of the derivation.

For example, assume that the first three productions of $ G $ are (in this order)

$$ S \rightarrow aCD,\ \ CD \rightarrow D ,\ \ D \rightarrow d . $$

Assume, further, that $ a $ and $ D $ are the second and third letter of $ \Sigma _ {1} $, respectively. (Recall that $ S = a _ {1} $.) Consider the word $ w = ad $. Clearly, $ w $ has the following derivation:

$$ \tag{a4 } S \Rightarrow aCD \Rightarrow aD \Rightarrow ad. $$

Then a solution for $ PCP $ is constructed according to the table below.

<tbody> </tbody>
$ 1 $ $ 4+ 2r+ 1 $ $ 2 $ $ 4+ r+ 2 $ $ 4+ 2r+ n+ 2 $ $ 3 $ $ 4+ 2 $ $ 4+ 3 $ $ 2 $ $ 4+ r+ 2 $ $ 4+ 2r+ n+ 3 $ $ 4 $
$ g $ $ BS\# $ $ a ^ \prime C ^ \prime D ^ \prime $ $ \# ^ \prime $ $ a $ $ D $ $ \# $ $ a ^ \prime $ $ D ^ \prime $ $ \# ^ \prime $ $ a $ $ d $ $ E $
$ h $ $ B $ $ S $ $ \# $ $ a ^ \prime $ $ C ^ \prime D ^ \prime $ $ \# ^ \prime $ $ a $ $ D $ $ \# $ $ a ^ \prime $ $ D ^ \prime $ $ \# ^ \prime adE $

Hence the word

$$ 1( 4+ 2r+ 1) 2( 4+ r+ 2)( 4+ 2r+ n+ 2) $$

$$ 3( 4+ 2)( 4+ 3) 2( 4+ r+ 2)( 4+ 2r+ n+ 3) 4 $$

(where parentheses have been added for clarity) is a solution for $ PCP $, the common value of the morphisms $ g $ and $ h $ being for this word:

$$ \tag{a5 } BS \# a ^ \prime C ^ \prime D ^ \prime \# ^ \prime aD\# a ^ \prime D ^ \prime \# ^ \prime adE . $$

Clearly, (a5) results from (a4) after the following simple modifications. The boundary markers $ B $ and $ E $ are added to the beginning and end; the sign $ \Rightarrow $ is replaced by $ \# $; moreover, every second step is primed, as is every second marker $ \# $; finally, an "idle" step (from $ aD $ to $ a ^ \prime D ^ \prime $) is added in order to reach the non-primed word $ ad $ corresponding to the final index of (a4).

It is easily seen that an analogous argument is valid in general: whenever $ w $ is in $ L( G) $, then $ PCP $ has a solution (see [a4], where this fact is established by a detailed inductive argument). It is somewhat more difficult to establish the converse — that is, to show that if $ PCP $ has a solution, then $ w $ is in $ L( G) $, see [a4].

Using a simple encoding it can be shown that the Post correspondence problem remains undecidable if the range alphabet $ \Delta $ of the morphisms $ g $ and $ h $ consists of two letters only. The decidability in case the domain alphabet $ \Sigma $ consists of two letters was established in [a1]. Another non-trivial decidable subclass, [a2], consists of instances $ ( g, h) $ where one of the morphisms $ g $ and $ h $ is periodic, that is, all of its values are powers of a single word. The Post correspondence problem remains undecidable if $ \Sigma $ consists of 9 letters. The decidability status is open if the cardinality of $ \Sigma $ is a fixed number between 3 and 8 (inclusive).

The Post correspondence problem is closely linked with equality sets, which are important in the representation theory of formal languages. By definition, the equality set of $ g $ and $ h $ consists of all words $ w $ such that $ g( w) = h( w) $. Clearly, an instance $ ( g, h) $ possesses a solution if and only if the equality set contains a non-empty word.

References

[a1] A. Ehrenfeucht, J. Karhumäki, G. Rozenberg, "The (generalized) Post corresponding problem with lists consisting of two words is decidable" Theor. Comp. Sc. , 21 (1982) pp. 119–144
[a2] J. Karhumäki, I. Simon, "A note on elementary homomorphisms and the regularity of equality sets" EATCS Bull. , 9 (1979) pp. 16–24
[a3] E. Post, "A variant of a recursively unsolvable problem" Bull. Amer. Math. Soc. , 52 (1946) pp. 264–268
[a4] A. Salomaa, "Formal languages" , Acad. Press (1987)
How to Cite This Entry:
Post correspondence problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Post_correspondence_problem&oldid=37351
This article was adapted from an original article by G. RozenbergA. Salomaa (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article