M. Margenstern, NONERASING TURING-MACHINES - A FRONTIER BETWEEN A DECIDABLE HALTING PROBLEM AND UNIVERSALITY, Theoretical computer science, 129(2), 1994, pp. 419-424
Citations number
7
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
A new criterion, namely, the number of colours used by the instruction
s of a Turing machine Program, is proposed to settle the frontier betw
een a decidable halting problem and universality for Turing machines.
The efficiency of this criterion has been proved by Pavlotskaia (1975)
for deterministic Turing machines on alphabet {0, 1}. It is used here
in the case of nonerasing Turing machines on the same alphabet.