NONERASING TURING-MACHINES - A FRONTIER BETWEEN A DECIDABLE HALTING PROBLEM AND UNIVERSALITY

Authors
MARGENSTERN M
Citation
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
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
129
Issue
2
Year of publication
1994
Pages
419 - 424
Database
ISI
SICI code
0304-3975(1994)129:2<419:NT-AFB>2.0.ZU;2-3
Abstract
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.