Another proof of undecidability for the correspondence decision problem - Had I been Emil Post

2014/11/19 by Vesa Halava, Halava, Vesa
Computer Science · #03D03 #03D35 #68Q01 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.DM #cs.LO #msc:03D03 #msc:03D35 #msc:68Q01

paper · pdf · doi:10.48550/arxiv.1411.5197

5 pages, manuscript

arxiv created 2014/11/19 · arxiv updated 2014/11/20

Abstract

In 1946 Emil Leon Post (Bulletin of Amer. Math. Soc. 52 (1946), 264 - 268) defined a famous correspondence decision problem which is nowadays called the Post Correspondence Problem, and he proved that the problem is undecidable. In this article we follow the steps of Post, and give another, simpler and more straightforward proof of the undecidability of the problem using the same source of reduction as Post original did, namely, the Post Normal Systems.

Related

• (Generalized) Post Correspondence Problem and semi-Thue systems
• On effective undecidability and Post's problem
• Threefold Post Correspondence System
• On Bi-infinite and Conjugate Post Correspondence Problems
• Variations on the Post Correspondence Problem for free groups