A variant of a recursively unsolvable problem. (English) Zbl 0063.06329

From the text: By a string on \(a,b\) we mean a row of \(a\)’s and \(b\)’s such as \(baabbbab\). It may involve only \(a\), or \(b\), or be null. If, for example, \(g_1, g_2, g_3\) represent strings \(bab\), \(aa\), \(b\) respectively, string \(g_2g_1g_1g_3g_2\) on \(g_1, g_2, g_3\) will represent, in obvious fashion, the string \(aababbabbaa\) on \(a,b\). By the correspondence decision problem we mean the problem of determining for an arbitrary finite set \((g_1, g'_1)\), \((g_2, g'_2), \ldots, (g_\mu, g'_\mu)\) of pairs of corresponding non-null strings on \(a, b\) whether there is a solution in \(n\), \(i_1, i_2, \ldots, i_n\) of equation
\[ g_{i_1}g_{i_2}\cdots g_{i_n}=g'_{i_1}g'_{i_2}\cdots g'_{i_n},\quad n\geq 1, i_j=1,2,\ldots,\mu.\tag{1} \]
That is, whether some non-null string on \(g_1,g_2, \ldots, g_n\), and corresponding string on \(g'_1,g'_2, \ldots, g'_n\) represent identical strings on \(a, b\).
In special cases, of course, the question posed by (1) may be answerable. Thus, if, with \(\mu=3\), \((g_1, g'_1)\), \((g_2, g'_2)\), \((g_3, g'_3)\) are \((bb, b)\), \((ab, ba)\), \((b, bb)\) respectively, \(g_1g_2g_2g_3 = bbababb=g'_1g'_2g'_2g'_3\), and (1) has a solution. Again, if each \(g_i\) is of greater length than the corresponding \(g'_i\), or if each \(g_i\) starts with a different letter than the corresponding \(g'_i\), (1) has no solution. We proceed to prove, on the other hand, that in its full generality the correspondence decision problem is recursively unsolvable, and hence, no doubt, unsolvable in the intuitive sense.


03D99 Computability and recursion theory
Full Text: DOI


[1] Alonzo Church, An Unsolvable Problem of Elementary Number Theory, Amer. J. Math. 58 (1936), no. 2, 345 – 363. · Zbl 0014.09802 · doi:10.2307/2371045
[2] Wilfried Sieg, Step by recursive step: Church’s analysis of effective calculability, Bull. Symbolic Logic 3 (1997), no. 2, 154 – 180. · Zbl 0884.03001 · doi:10.2307/421012
[3] Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197 – 215. · Zbl 0063.06327 · doi:10.2307/2371809
[4] Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284 – 316. · Zbl 0063.06328
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.