22 Mai - 28 Mai


Retour à la vue des calendrier
Mardi 23 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Magouilles diverses pour les machines à signaux
Description: Thierry Monteil 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 connupour être équivalent au modèle de BlumShubSmale linéaire. Nousconstruirons dans ce cadre un oracle universel optimal (en nombre devitesses et de paramètres irrationnels). Nous verrons comment jouer aubillard permet semi-décider l'algébricité d'un nombre réel alors que c'estimpossible dans le modèle BSS-linéaire. Nous verrons comment modifierlégèrement le modèle pour obtenir un modèle équivalent au modèle BSSstandard.Lorsque l'on permet aux accumulations d'événements de produire un signal,nous verrons, en jouant sur l'alternance discret/continu, commentconstruire des machines dont le pouvoir dépasse largement les modèles decalcul 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ètreM(p) telle que toute suite N->[0,1] est generèe un certain M(p). une "fonction analytique universelle", c'est à dire une machine avec2 parametres t,x telle que pour toute fonction analytique f de rayon deconvergence >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çantun curseur. aussi, on peut prendre en compte la géométrie du modèle dans laformulation 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ésen rouge, l'ensemble de leurs accumulations au temps 1 est un compact. Ilse trouve que cette restriction est la seule : il existe une machine à unparametre M(p) telle que pour tout compact K inclus dans [0,1], il existep dans [0,1] tel que l'ensemble des accumulations rouges de M(p) au temps1 est K.L'exposé sera informel et sa compréhension ne nécessitera pas de prérequis.