Defensa Tesis Licenciatura Andrés Taraciuk

• Título: Nociones de aleatoriedad y transformaciones de cambio de base
• Director: Santiago Figueira
• Jurado: Verónica Becher y Sergio Daicz
• Resumen:

Aunque es razonable pensar que cualquier noción de aleatoriedad debe ser invariante por una transformación sencilla como el cambio de base, no se ha prestado mucha atención a este fenómeno. En los casos conocidos, las demostraciones resultan bastante complicadas. En esta tesis trabajamos con distintas nociones formales de aleatoriedad para representaciones de los números reales en distintas bases.

Para el paradigma de aleatoriedad vía martingalas con recursos acotados, probamos que n*log^3n-aleatoriedad implica normalidad, siguiendo la representación tradicional en base 2. Extendemos este resultado para probar que n*log^3n-aleatoriedad en base b implica normalidad en base b, para cualquier base b mayor o igual a 2. Este resultado va en la dirección de encontrar nuevos algoritmos para computar números absolutamente normales.

Estudiamos una demostración de que aleatoriedad de Martin-Löf es invariante por cambio de base presentada por Calude en 1994. Detectamos y corregimos errores no triviales que aparecen en esa demostración.

Damos una demostración nueva (a nuestro modo de ver, más directa, sencilla y corta que aquella presentada por Calude), de que Martin-Löf aleatoriedad es invariante por cambio de base, y adaptamos el resultado para las nociones de aleatoriedad de Schnorr y de Kurtz.

Por último, planteamos una conjetura acerca de la invarianza por cambio de base de t(n)-aleatoriedad, y damos un esquema nuevo que podría ser usado para construir números absolutamente normales.