debugMinor
Is Post's Correspondence Problem decidable with fixed word size?
Viewed 0 times
problemwithsizepostdecidablewordcorrespondencefixed
Problem
So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$.
I'm wondering, can anything similar be said for when there is a fixed word length?
To be precise, here's the problem:
Given fixed $m$ and $n$, with $n \geq 7$, and words
$u_1, \ldots u_n$ and $v_1 \ldots v_n$ such that $|u_i| \leq m$ and $|v_i| \leq m$,
is there an index sequence $i_1, \ldots i_k$ such that
$u_{i_1} \cdots u_{i_k} = v_{i_1} \cdots v_{i_k}$.
For what values of $m$, if any, is this known to be undecidable?
Note that this is similar to this question, but none of the 8 linked papers seemed by their titles to answer my question, and I haven't fully read all 8 of them yet.
I'm wondering, can anything similar be said for when there is a fixed word length?
To be precise, here's the problem:
Given fixed $m$ and $n$, with $n \geq 7$, and words
$u_1, \ldots u_n$ and $v_1 \ldots v_n$ such that $|u_i| \leq m$ and $|v_i| \leq m$,
is there an index sequence $i_1, \ldots i_k$ such that
$u_{i_1} \cdots u_{i_k} = v_{i_1} \cdots v_{i_k}$.
For what values of $m$, if any, is this known to be undecidable?
Note that this is similar to this question, but none of the 8 linked papers seemed by their titles to answer my question, and I haven't fully read all 8 of them yet.
Solution
For all $m \geq 3$, the problem is undecidable.
Proof by reduction from the word problem of unrestricted grammars:
-
Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have length at most $3$.
This can be seen by translating any grammar into an equivalent TM and then converting back.
-
Map the resulting grammar to PCP instances; no tile is longer than the longest left or right side of a rule.
That is, with step 1, all tiles have length $\geq 3$.
Proof by reduction from the word problem of unrestricted grammars:
-
Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have length at most $3$.
This can be seen by translating any grammar into an equivalent TM and then converting back.
-
Map the resulting grammar to PCP instances; no tile is longer than the longest left or right side of a rule.
That is, with step 1, all tiles have length $\geq 3$.
Context
StackExchange Computer Science Q#28787, answer score: 9
Revisions (0)
No revisions yet.