MACHINE UNIVERSELLE NON-EFFACANTE SUR (0,1) A TROIS INSTRUCTIONS GAUCHES

M. Margenstern

IBP-Litp 1994/08: Rapport de Recherche Litp / Litp research reports
29 pages - Décembre/December 1994 - French document.

PostScript : Ko /Kb

Titre / Title: MACHINE UNIVERSELLE NON-EFFACANTE SUR (0,1) A TROIS INSTRUCTIONS GAUCHES

Résumé : Un nouveau résultat de frontière entre la décidabilité de l'arrêt et l'universalité est énoncé pour les machines déterministes non effaçantes sur (0,1). Plus précisément : pour toute machine de cette sorte avec au plus deux instructions gauches le problème de l'arrêt est décidable et il en existe une avec exactement trois instructions gauches qui simule une machine de Turing universelle. De plus, on peut construire une telle machine universelle avec 218 états. Dans ce rapport nous donnons une preuve détaillée du résultat qui concerne la machine ayant exactement trois instructions gauches et qui simule une machine de Turing universelle.

Abstract : A new frontier between a decidable halting problem and universality for deterministic non erasing Turing machines on (0,1) is stated. Namely : any machine of this kind with at most two left instructions has a decidable halting problem and there is a machine of this kind with precisely three left instructions which simulates a universal Turing machine. Moreover, such a universal Turing machine with 218 states can be consrtucted. In this report, we give a thorough proof of the result which deals with the machine that have precisely three left instructions and that mimicks a universal Turing machine.

Publications internes Litp 1994 / Litp research reports 1994