Nonerasing Turing machines: a frontier between a decidable halting problem and universality

AbstractA 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 Pavlotskaïa (1975) for deterministic Turing machines on alphabet {0,1}. It is used here in the case of nonerasing Turing machines on the same alphabet