Deux machines de Turing universelles :l'une sur {0,1} avec deux instructions gauches, l'autre sur {0,1,2} avec une seule instruction gauche.

M. MARGENSTERN, L. PAVLOTSKAIA

IBP-Litp 1995/25: Rapport de Recherche Litp / Litp research reports
16 pages - Juin/June 1995 - French document.

PostScript : Ko /Kb

Titre / Title: Deux machines de Turing universelles :l'une sur {0,1} avec deux instructions gauches, l'autre sur {0,1,2} avec une seule instruction gauche.

Résumé : On constuit une machine de Turing universelle sur l'alphabet {0, 1} dont le programme contient exactement deux instructions de mouvement gauche et une machine de Turing universelle sur l'alphabet {0,1} dont le programme contient une unique instruction de mouvement gauche.

Abstract : A universal Turing machine is constructed on alphabet { 0,1 } , the program of which contains precisely two instructions involving left moves; Another one is constructed on { 0,1,2} with a single instruction involving a left move.

Publications internes Litp 1995 / Litp research reports 1995