โพสต์ปัญหาการติดต่อ

Post Correspondence Problem (PCP) ซึ่งนำเสนอโดย Emil Post ในปี 1946 เป็นปัญหาในการตัดสินใจที่ไม่สามารถตัดสินใจได้ ปัญหา PCP บนตัวอักษร ∑ ระบุไว้ดังนี้ -

ให้สองรายการต่อไปนี้ M และ N ของสตริงที่ไม่ว่างเปล่าเหนือ ∑ -

M = (x ₁ , x ₂ , x ₃ , ......... , x _n )

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

เราสามารถพูดได้ว่ามี Post Correspondence Solution ถ้าสำหรับ 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
ม	Abb	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
ม	ก	bab	bbaaa
น	ก	บา	bab

ในกรณีนี้ไม่มีทางแก้ไขเนื่องจาก -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (ความยาวไม่เท่ากัน)

ดังนั้นจึงสามารถกล่าวได้ว่าปัญหาการโพสต์นี้คือ undecidable.