포스트 서신 문제

1946 년 Emil Post가 소개 한 Post Correspondence Problem (PCP)은 결정 불가능한 결정 문제입니다. 알파벳 ∑에 대한 PCP 문제는 다음과 같습니다.

다음 두 목록이 주어지면 MN 비어 있지 않은 문자열의 ∑ −

M이 = (X 1 , X 2 , X 3 , ........., X N )

N = (y 1 , y 2 , y 3 , ………, y n )

만약 i 1 , i 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
미디엄 씨줄 aa aaa
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
미디엄 ab bbaaa

이 경우 솔루션이 없습니다.

| x2x1x3 | ≠ | y2y1y3 | (길이는 동일하지 않습니다)

따라서이 Post Correspondence 문제는 undecidable.