Résumé : Les machines à signaux sont un modèle de calcul déterministe dont espace et temps sont continus.

Si les accumulations d'événements sont interdites, ce modèle est connu pour être équivalent au modèle de BlumShubSmale linéaire. Nous construirons dans ce cadre un oracle universel optimal (en nombre de vitesses et de paramètres irrationnels). Nous verrons comment jouer au billard permet semi-décider l'algébricité d'un nombre réel alors que c'est impossible dans le modèle BSS-linéaire. Nous verrons comment modifier légèrement le modèle pour obtenir un modèle équivalent au modèle BSS standard.

Lorsque l'on permet aux accumulations d'événements de produire un signal, nous verrons, en jouant sur l'alternance discret/continu, comment construire des machines dont le pouvoir dépasse largement les modèles de calcul usuels, en particulier, nous construirons

• une "courbe de Peano" c'est a dire une surjection de [0,1] dans [0,1]^2.
• un "oracle universel continu", c'est à dire un machine à un paramètre M(p) telle que toute suite N->[0,1] est generèe un certain M(p).
• une "fonction analytique universelle", c'est à dire une machine avec 2 parametres t,x telle que pour toute fonction analytique f de rayon de convergence >1, il existe t tel que f(x)=M(t,x) pour tout x dans [-1,1], en particulier, on peut calculer les fonctions exp(x), sin(), en déplaçant un curseur.
• aussi, on peut prendre en compte la géométrie du modèle dans la formulation même de ce que peut "calculer" (ou "dessiner") une machine, pas seulement un booléen, un entier ou un réel comme dans le cas discret. Étant donnée une machine M, si certains types de collisions sont coloriés en rouge, l'ensemble de leurs accumulations au temps 1 est un compact. Il se trouve que cette restriction est la seule : il existe une machine à un parametre M(p) telle que pour tout compact K inclus dans [0,1], il existe p dans [0,1] tel que l'ensemble des accumulations rouges de M(p) au temps 1 est K.

L'exposé sera informel et sa compréhension ne nécessitera pas de prérequis.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr