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

摘要

Dans un article antérieur, nous définissions un critère permettant de séparer les cas où une machine de Turing non-effaçante sur {0,1} possède un problème de l'arrêt décidable de ceux où l'on peut construire une machine de Turing universelle. En appliquant un théorème qui entraîne l'existence de la frontière qui vient d'être indiquée et des techniques analogues fondées sur l'étude qualitative des mouvements de la tête d'une machine de Turing sur son ruban, nous démontrons ici un autre résultat de frontière fondé sur un autre critère, à savoir le nombre d'instructions gauches. Dans cet article, nous donnons une démonstration complète de la partie "décidabilité" de ce résultat. Nous traitons aussi le cas d'une unique instruction gauche avec un alphabet fini quelconque dans un contexte non-effaçant généralisé. Posé au début des années soixante-dix, voir [9], le problème de la latéralité, résolu depuis sur l'alphabet {0,1} sans restriction, est maintenant complètement résolu dans le cas non-effaçant.%In a previous work, we defined a criterion which allowed to separate cases when all non-erasing Turing machines on {0,1} have a decidable halting problem from cases where a universal non-erasing machine can be constructed. Applying a theorem which entails the just indicated frontier and analogous techniques based upon a qualitative study of the motions of the head of a Turing machine on its tape, another frontier result is here proved, based upon a new criterion, namely the number of left instructions. In this paper, a complete proof of the decidability part of the result is supplied. The case of a single left instruction with a finite alphabet in a generalized non-erasing context is also delt with. Thus, the laterality problem, raised in the early seventies, see [9], solved on {0,1} alphabet without restriction, is now completely solved in the non-erasing case.