Cegielski
Le Jeudi 29 mars 2001 à 14h30
au LRI, Salle 101
(Université Paris 12)
Les arithmétiques faibles
Résumé/Abstract :
Les ``arithmétiques faibles´´
concernent le point de jonction
entre la théorie des nombres et la logique. Je vais donner
dans cet exposé quelques-uns de mes résultats de ce
domaine, montrant :
- des problèmes de décidabilité
(arithmétique de Presburger (N,+), arithmétique de
Skolem (N,.) ou (N,C(x,y),S), où C
est la fonction de Cantor et S la fonction successeur) ;
- des problèmes de démonstration élémentaire
en théorie des nombres (par exemple le théorème de
Dirichlet dans l'arithmétique de Peano et en-dessous) ;
- des applications de la complexité (par exemple la
non-définissabilité de la multiplication dans
(N,divise)) ;
- des problèmes d'algorithmique (par exemple la
détermination du nombre de fenêtres contenant une sous-suite
[les lettres ne sont pas nécessairement consécutives] dans un
mot donné) ;
- des études de suites entières (par exemple la suite
d'Erdös-Woods introduite récemment).