déCIDABILITE DU PROBLèME DE L'ARRêT POUR LES MACHINES DE TURING NON eFFACANTES SUR (0,1) ET A 2 INSTRUCTIONS GAUCHES

M. MARGENSTERN

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

PostScript : Ko /Kb

Titre / Title: déCIDABILITE DU PROBLèME DE L'ARRêT POUR LES MACHINES DE TURING NON eFFACANTES SUR (0,1) ET A 2 INSTRUCTIONS GAUCHES

Résumé : On énonce une nouvelle frontière entre la décidabilité du problème de l'arrêt et l'universalité pour les machines de Turing déterministes et non effaçantes sur (0,1) . De façon précise : toute machine de ce type qui a au plus deux instructions gauches a un problème de l'arrêt décidable et il existe une machine de ce type avec exactement trois instructions gauches qui simule une machine de Turing universelle. De plus, on ne peut construire une telle machine de Turing universelle avec 223 états. Dans ce rapport, on donne une preuve complète du résultat qui concerne les machines qui ont au plus deux insrtructions gauches.

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 223 states can be constructed. In this report, we give a thorough proof of the result which deals with the machines that have at most two left instructions.

Publications internes Litp 1994 / Litp research reports 1994