THE LATERALITY PROBLEM FOR NON-ERASING TURING-MACHINES ON (0,1) IS COMPLETELY SOLVED

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.