Ist das Korrespondenzproblem von Post bei fester Wortgröße entscheidbar?

Es ist also bekannt, dass PCP selbst dann unentscheidbar ist, wenn wir die Anzahl der Kacheln auf festlegen .$n \geq 7$

Ich frage mich, kann etwas Ähnliches gesagt werden, wenn es eine feste Wortlänge gibt?

Um genau zu sein, hier ist das Problem:

Bei festem und mit und den Wörtern und $m$$n$$n \geq 7$$u_1, \ldots u_n$$v_1 \ldots v_n$ so dass $|u_i| \leq m$ und $|v_i| \leq m$Gibt es eine Indexsequenz? $i_1, \ldots i_k$ so dass $u_{i_1} \cdots u_{i_k} = v_{i_1} \cdots v_{i_k}$.

Für welche Werte von $m$Ist dies bekanntermaßen unentscheidbar?

Beachten Sie, dass dies dieser Frage ähnlich ist , aber keines der 8 verknüpften Artikel nach ihrem Titel meine Frage zu beantworten schien, und ich habe noch nicht alle 8 vollständig gelesen.

Für alle $m \geq 3$ist das Problem unentscheidbar.

Beweis durch Reduktion aus dem Wortproblem der uneingeschränkten Grammatik:

1. Nehmen Sie eine beliebige formale Grammatik. Wlog alle linken und rechten Seiten von Regeln haben höchstens Länge$3$.

   Dies kann festgestellt werden, indem eine beliebige Grammatik in ein äquivalentes TM übersetzt und dann zurückkonvertiert wird .

2. Ordnen Sie die resultierende Grammatik PCP-Instanzen zu . Keine Kachel ist länger als die längste linke oder rechte Seite einer Regel.

   Das heißt, mit Schritt 1 haben alle Kacheln eine Länge $\geq 3$.