Una perspectiva computacional sobre números normales
La normalidad es una forma débil de azar. Un número real es normal enuna base entera dada si su expansión en esa base es balanceada: todos los bloques dela misma cantidad de dígitos tienen igual frecuencia en la expansión. La normalidadabsoluta es normalidad en toda base. En esta tesis resolvemos va...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis doctoral publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
2014
|
| Materias: | |
| Acceso en línea: | https://hdl.handle.net/20.500.12110/tesis_n5450_Heiber |
| Aporte de: |
| Sumario: | La normalidad es una forma débil de azar. Un número real es normal enuna base entera dada si su expansión en esa base es balanceada: todos los bloques dela misma cantidad de dígitos tienen igual frecuencia en la expansión. La normalidadabsoluta es normalidad en toda base. En esta tesis resolvemos varios problemassobre normalidad: La existencia de números absolutamente normales computables era conocida,pero no se conocía ningún algoritmo que computara uno en tiempo polinomial. Nosotros damos un algoritmo que computa uno en tiempo apenas mayor acuadrático. Mostramos que el conjunto de números absolutamente normales, como subconjuntode los reales, no tiene otras propiedades aritméticas que las impuestaspor la definición de normalidad. Técnicamente, demostramos que el conjuntode números absolutamente normales es π°3-completo. Extendemos la caracterización conocida de normalidad en términos de incompresibilidadmediante autómatas finitos. Analizamos exhaustivamente todaslas maneras de mejorar un simple autómata finito agregando memoria de diferentesformas, permitiendo no-determinismo y permitiendo la lectura de la entradamás de una vez. Demostramos que la normalidad se preserva bajo reglas de selección basadasen préfijos finitos o sufijos infinitos reconocidos por autómatas finitos, pero noambos simultáneamente. Esto extiende un resultado conocido para el caso deprefijos. |
|---|