通信後の問題
1946年にEmilPostによって導入されたPostCorrespondence Problem（PCP）は、決定不可能な決定問題です。アルファベット∑のPCP問題は次のように述べられています-
次の2つのリストを考えると、 M そして N ∑ −上の空でない文字列の数
M =（x 1、x 2、x 3、………、x n）
N =（y 1、y 2、y 3、………、y n）
いくつかの私のためならば私たちは、ポストの対応策があると言うことができる1私は、2、............ I K 1≤I、J ≤nは、条件X I1 ...... .X IK = Y I1 ......が。 Y IKを満たします。
例1
リストかどうかを確認します
M =（abb、aa、aaa）およびN =（bba、aaa、aa）
通信後のソリューションがありますか？
解決
| x 1 | x 2 | x 3 | |
|---|---|---|---|
| M | アッブ | aa | aaa |
| N | Bba | aaa | aa |
ここに、
x2x1x3 = ‘aaabbaaa’
そして y2y1y3 = ‘aaabbaaa’
私たちはそれを見ることができます
x2x1x3 = y2y1y3
したがって、解決策は i = 2, j = 1, and k = 3.
例2
リストかどうかを確認します M = (ab, bab, bbaaa) そして N = (a, ba, bab) 通信後のソリューションがありますか？
解決
| x 1 | x 2 | x 3 | |
|---|---|---|---|
| M | ab | バブ | bbaaa |
| N | a | ba | バブ |
この場合、次の理由で解決策はありません。
| x2x1x3 | ≠ | y2y1y3 | （長さは同じではありません）
したがって、この通信後の問題は次のようになります。 undecidable。