M. Margenstern, THE LATERALITY PROBLEM FOR NON-ERASING TURING-MACHINES ON (0,1) IS COMPLETELY SOLVED, Informatique theorique et applications, 31(2), 1997, pp. 159-204
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
In a previous work, [2], we defined a criterion which allowed to separ
ate cases when all non-erasing Turing machines on {0,1} have a decidab
le halting problem from cases where a universal non-erasing machine ca
n be constructed. Applying a theorem which entails the just indicated
frontier and analogous techniques based upon a qualitative study of th
e motions of the head of a Turing machine on its tape, another frontie
r result is here proved, based upon a new criterion, namely the number
of left instructions. In this paper, a complete proof of the decidabi
lity part of the result is supplied. The case of a single left instruc
tion with a finite alphabet in a generalized non-erasing context is al
so delt with. Thus, the laterality problem raised in the early seventi
es, see [9], solved on {0,1} alphabet without restriction, is now comp
letely solved in the non-erasing case.