5
$\begingroup$

So, I'm refreshing my undecidablility knowledge, and I came across this statement reading about Post's Correspondence Problem on Wikipedia:

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.

I'm a little confused about how to parse this sentence formally.

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} \}$

Which of the following is true?

  • $\forall n \ldotp n \geq 5 \implies POST(n)$ is undecidable
  • $\bigcup_{n \geq 5} POST(n)$ is undecidable

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?

$\endgroup$
  • 1
    $\begingroup$ The statement of Wikipedia that you quote is the first one: for all $n \ge 5$, $POST(n)$ is undecidable. But the sketch proof they give only proves your second statement (because the size of the tileset depends on the number of states in the TM). $\endgroup$ – xavierm02 Mar 13 '17 at 22:51
4
$\begingroup$

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

A. EHXENFEUCHT, J. KARHUMAKI, G. ROZENBERG, "THE (GENERALIZED) POST CORRESPONDENCE PROBLEM WITH LISTS CONSISTING OF TWO WORDS IS DECIDABLE", Theoretical Computer Science 21 (1982) 119-144.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.