Small deterministic Turing machines (Q1349854)

Small deterministic Turing machines with one bi-infinite tape and one scanning head are considered. Let \(DTM(m,n)\) denote the class of all such machines with \(m\) tape symbols (including the blank) and \(n\) states (excluding the halting state). It is known that there exist universal Turing machines in \(DTM(5,6)\) and in \(DTM(4,7)\). It is also known that the halting problem for all machines from \(DTM(1,n)\) and \(DTM(m,1)\) is decidable. The first fact is trivial whereas the second one has been shown by \textit{G. T. Herman} [Z. Math. Logik Grundlagen Math. 14, 185-191 (1968; Zbl 0169.31104)]. \textit{M. L. Minsky} [Proc. Symp. Pure Math. 5, 229-238 (1962; Zbl 0192.06601); Computation: finite and infinite machines (1967; Zbl 0195.02402)] mentioned that the halting problem for \(DTM(2,2)\) is decidable too; however without giving any proof and stating only that this result is unpublished and unpublishable. In such a state it remained since 1961 or 1972, respectively, until 1988. By a reduction to few cases it was possible to solve the problem and bring it into a publishable form. A first version can be found in a paper of \textit{V. Diekert} and \textit{M. Kudlek} [``Small deterministic Turing machines'', Papers on Automata and Languages, Dep. Math., Karl-Marx Univ. Econ., Budapest 1988-4, 77-87 (1989)]. At that time the results from 1975 [\textit{L. M. Pavlotskaya}, Probl. Kibern. 33, 91-118 (1978; Zbl 0426.68025)] stating the halting problem to be decidable for \(DTM(2,2)\) and \(DTM (2,3)\) have not been known to the authors. In that paper a completely different method was used. Neither were known the results by \textit{Yu. V. Rogozhin} [Mat. Issled. 69, 76-90 (1982; Zbl 0515.03020)] stating that there are universal Turing machines in \(DTM(2,24)\), \(DTM (3,11)\), \(DTM(5,5)\), \(DTM(6,4)\), \(DTM(10,3)\), and \(DTM(21,2)\). All these results were only little known in Western countries before 1991. It is also shown that the sets accepted by machines from \(DTM(2,1)\) are regular, and that those accepted by machines from \(DTM(3,1)\) are regular too, except one case giving a deterministic linear context-free language which is essentially the nonregular language \(L=\{a^nb^n|1\leq n\}\). The languages accepted by machines from \(DTM(2,2)\) are also regular, except one case (up to symmetries) giving essentially the same language as in the exceptional case of \(DTM(3,1)\), namely a deterministic linear context-free language. Thus, the halting problem is decidable for \(DTM(2,2)\). To obtain this result several symmetries are used to reduce the number of machines to consider. Finally, also a machine from \(DTM(4,4)\) is presented accepting a context-sensitive language, essentially \(L= \{a^k|k=2^n,\;0\leq n\}\).