UNDECIDABILITY OF INFINITE POST CORRESPONDENCE PROBLEM FOR INSTANCES OF SIZE 8

摘要

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231-245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO-Theor. Inf. Appl. 40 (2006) 551-557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.