Dubacq
Le 26 Avril 2001 à 14h30
au LRI, Salle 101
(Université de Caen)
Variantes des machines de Turing
Résumé/Abstract :
Le modèle de la machine de Turing est un modèle de calcul bien
connu. Mais il est possible d'étudier des variantes de ce modèle,
introduites en particulier par la complexité de Kolmogorov, et de
s'interroger sur la notion de plongement d'un calcul qui reste en tout
point fini dans un ruban qui est potentiellement infini.