Abstract   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 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.
['Maurice Margenstern']
Nonerasing Turing machines: a frontier between a decidable halting problem and universality