Teorema de Cobham: Sistemas de numeración y dinámica simbólica

Ponente(s): Fabien Durand .

En esta charla nos interesa reconocer que tipos de algoritmos pueden reconocer si un entero pertenece o no a un subconjunto preestablecido. El Teorema de Cobham (1969) nos indica que la respuesta depende fuertemente de la base en la cual se escriben los enteros del subconjunto. En esta charla presentaremos una prueba dinámica del Teorema Cobham, mucho menos técnica que la demostración original. También, presentamos un panorama general de los trabajos inspirados por este teorema en los siguientes temas: aritmética de Presburger, logica, sistemas de funciones iteradas, trascendencia y sistemas de numeración no estándar.