포스트 서신 문제

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

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

M이 = (X ₁ , X ₂ , X ₃ , ........., X _N )

N = (y ₁ , y ₂ , y ₃ , ………, y _n )

만약 i ₁ , i ₂ , ………… 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

여기,

x₂x₁x₃ = ‘aaabbaaa’

과 y₂y₁y₃ = ‘aaabbaaa’

우리는 그것을 볼 수 있습니다

x₂x₁x₃ = y₂y₁y₃

따라서 해결책은 i = 2, j = 1, and k = 3.

예 2

목록 여부 찾기 M = (ab, bab, bbaaa) 과 N = (a, ba, bab) 포스트 서신 솔루션이 있습니까?

해결책

	x 1	x 2	x 3
미디엄	ab	밥	bbaaa
엔	ㅏ	바	밥

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

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (길이는 동일하지 않습니다)

따라서이 Post Correspondence 문제는 undecidable.