通信後の問題

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