Cheap and Secure Web Hosting Provider : See Now

[Solved]: Undecidability of the PCP problem with bounded width

, ,
Problem Detail:

Given two ordered sets of words \$a_1, a_2, ..., a_k\$, \$b_1, b_2, ..., b_k\$ taking values in some discrete alphabet \$A\$, a solution to the PCP problem is a sequence \$i_1, ..., i_n\$ taking values in \$1, 2,..., k\$ such that \$a_{i_1}|a_{i_2}|...|a_{i_n}=b_{i_1}|b_{i_2}|...|b_{i_n}\$ where \$|\$ means concatenation. \$k\$ can be called the length of the problem, \$n\$ the length of the solution and if we let \$w\$ be the length of the largest word in \$a_1, a_2, ..., a_k, b_1, b_2, ..., b_k\$, \$w\$ is called the width of the problem.

I know that the PCP problem becomes decidable in several scenarios, for instance: for bounded \$n\$, or if \$A\$ is unary, etc. On the other hand for \$k\geq7\$ PCP is still undecidable. My question is, is there any result known for bounded values of \$w\$?

If \$w\$ is bounded, and the alphabet size is bounded, then the number of possible words is bounded. Thus, there is only a finite number of possible instances, so the problem becomes a finite languages, and hence decidable.

If you don't bound the alphabet, then you can encode any width of \$w\$ by adding more letters, so the problem is the same as standard PCP, and hence undecidable.