# Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$

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?

• 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). – xavierm02 Mar 13 '17 at 22:51

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