Vers une nouvelle approche de l'Université concernant les machines de Turing

M. Margenstern, L. Pavlotskaïa

IBP-Litp 1995/58: Rapport de Recherche Litp / Litp research reports
23 pages - Novembre/November 1995 - French document.

PostScript : Ko /Kb

Titre / Title: Vers une nouvelle approche de l'Université concernant les machines de Turing

Résumé : On considère une nouvelle machine constituée par le couplage d'une machine de Turing avec un automate. On obtient ainsi des machines de Turing universelles avec un très petit nombre d'instructions, respectivement huit et cinq avec un automate fini. Ceci améliore un résultat précédent de L. Pavlotskaïa obtenant dix-sept instructions avec un automate fini très simple.

Mots-clés : Calculabilité, machines.

Abstract : A new machine is considered, which consists of a Turing machine connected with an automaton. Turing machines are such a way obtained with a very small number of instructions, respectively eight and five with a finite automaton. This improves a preceding result by L. Pavlotskaya who obtained seventeen instructions with a very simple finite automaton.

Keywords: Calculability, machines.

Publications internes Litp 1995 / Litp research reports 1995