10 octobre 2016
Paul-Elliot Anglès d'Auriac (LACL)Traditionnelement, la théorie de la calculablilité se fait dans l’espace de Cantor : l’espace des suites infinies de 0 et de 1. Cependant, il est possible de définir ce qu’est un élément calculable, une fonction calculable, dans des espaces plus généraux. Cela nous permet par exemple de définir un calcul prenant en entrée un réél sans passer par sa représentation en binaire.
Un de ces espaces, le cube de Hilbert ([0;1]^N), présente la particularité de posséder des éléments qui ne sont calculatoirement équivalents à aucun élément de l’espace de Cantor. Les degrés du cube de Hilbert sont appelés degrés continus.
Dans cette exposé nous allons voir comment un théorème de calculabilité classique s’étend aux degrés continus : le lemme de Schoenfield, qui affirme que X est calculable en le problème de l’arret si et seulement si on peut calculer une suite qui converge vers X.