Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$ - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:44:49Z https://cs.stackexchange.com/feeds/question/71502 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/71502 5 Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$ jmite https://cs.stackexchange.com/users/2253 2017-03-13T22:03:00Z 2017-03-13T23:21:49Z <p>So, I'm refreshing my undecidablility knowledge, and I came across this statement reading about Post's Correspondence Problem on <a href="https://en.wikipedia.org/wiki/Post_correspondence_problem" rel="noreferrer">Wikipedia</a>:</p> <blockquote> <p>A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4. </p> </blockquote> <p>I'm a little confused about how to parse this sentence formally.</p> <p>Let $POST(n) = \\ \{((a_1, b_1),\ldots, (a_n, b_n) \mid a_i, b_i \in \{0,1\}^*, \\ \exists j_1 \ldots j_m \ldotp a_{j_1} \cdots a_{j_m} = b_{j_1} \cdots b_{j_m} \}$</p> <p>Which of the following is true?</p> <ul> <li>$\forall n \ldotp n \geq 5 \implies POST(n)$ is undecidable</li> <li>$\bigcup_{n \geq 5} POST(n)$ is undecidable</li> </ul> <p>i.e. if I'm showing that a problem is undecidable, can I show that that problem can be used to solve any 5-tile PCP instance? Or am I not allowed to make such assumptions on the number of tiles?</p> https://cs.stackexchange.com/questions/71502/is-posts-problem-undecidable-for-fixed-number-of-tiles-i-e-n-geq5/71504#71504 4 Answer by Maczinga for Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$ Maczinga https://cs.stackexchange.com/users/66639 2017-03-13T23:21:49Z 2017-03-13T23:21:49Z <p>It is the first version: $\forall n,\,n\geq 5\Rightarrow\,POST(n)$ is undecidable. The reason for the number $5$ is explained in the article of Turlough Neary cited in wikipedia page. The case $n=2$ is proven in</p> <p>A. EHXENFEUCHT, J. KARHUMAKI, G. ROZENBERG, <em>"THE (GENERALIZED) POST CORRESPONDENCE PROBLEM WITH LISTS CONSISTING OF TWO WORDS IS DECIDABLE"</em>, Theoretical Computer Science 21 (1982) 119-144.</p>