Non erasing Turing machines: A frontier between a decidable halting problem and universality. (English) Zbl 0794.68047

Ésik, Zoltán (ed.), Fundamentals of computation theory. 9th international conference, FCT ’93, Szeged, Hungary, August 23-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 710, 375-385 (1993).
Summary: A new criterion, namely the number of colours used by the instructions of a Turing machine program, is proposed to settle the frontier between a decidable halting problem and universality for Turing machines. The efficiency of this criterion has been proved by L. M. Pavlotskaya [Math. Notes 13, 537-541 (1973), translation from Mat. Zametki 13, 899- 909 (1973; Zbl 0284.02017); Diskret. Analiz, Nowsibirsk 27, 52-60 (1975; Zbl 0322.02036)], for deterministic Turing machines on alphabet \(\{0,1\}\). It is used here in the case of nonerasing Turing machines on the same alphabet.
For the entire collection see [Zbl 0875.00104].


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions