Catálogo de publicaciones - tesis

Compartir en
redes sociales

Título de Acceso Abierto

Aspectos de aleatoriedad

Santiago Daniel Figueira Verónica Andrea Becher

publishedVersion.

Resumen/Descripción – provisto por el repositorio digital

En esta tesis, investigamos algunos aspectos de aleatoriedad y trivialidad definidos por la teoría de largo de programa. Primero abordamos la aleatoriedad y la absoluta normalidad de números reales. Ambos conjuntos de reales tienen medida de Lebesgue 1 y son nociones que implican varias propiedades de estocasticidad. A pesar de esto, no ha sido fácil dar ejemplos concretos en estas clases. Probamos que existen números absolutamente normales que son computables y damos dos algoritmos para construirlos. El primero está basado en una reformulación computable de un resultado de Sierpinski de 1916. El segundo es parte de nuestra reconstrucción de un manuscrito inédito de Turing sobre números normales. En cuanto a ejemplos de aleatoriedad, generalizamos la probabilidad de detención de Chaitin y analizamos la probabilidad de que una máquina universal se detenga y devuelva un resultado en un conjunto dado X. Estudiamos la relación entre las propiedades de X provenientes de la teoría de la computabilidad y las propiedades de aleatoriedad de la probabilidad inducida. El segundo aspecto de aleatoriedad que tratamos es el estudio de una variante de la complejidad clásica de largo de programa que no involucra oráculos, y nos preguntamos si esta noción conduce a una definición más estricta de aleatoriedad. Definimos nuestra función de complejidad en base a máquinas de Turing monótonas que realizan cómputos infinitos. Investigamos algunas propiedades de esta función y consideramos las definiciones inducidas de aleatoriedad y trivialidad. Con esta última noción caracterizamos a los reales computables. El último aspecto se vincula con la anti-aleatoriedad y la posibilidad de caracterizar a los reales llamados K-triviales con nociones que no involucren directamente a la complejidad de largo de programa libre de prefijos. Proponemos e investigamos dos nociones de lowness que tienen sus raíces puramente en la teoría de la computabilidad, reforzando otras ya existentes en la literatura. Relacionamos la complejidad de largo de programa plana C y libre de prefijos K con estas nociones, considerando variaciones de K-trivialidad y C-trivialidad. Concluimos con una lista de las principales preguntas que quedaron abiertas.

Palabras clave – provistas por el repositorio digital

TEORIA ALGORITMICA DE LA INFORMACION; TEORIA DE LA COMPUTABILIDAD; COMPLEJIDAD DE LARGO DE PROGRAMA; COMPLEJIDAD DE KOLMOGOROV; NUMEROS NORMALES; NUMEROS ABSOLUTAMENTE N0RMALES; ALEATORIEDAD; NUMERO OMEGA DE CHAITIN; PROBABILIDAD DE DETENCION; JERARQUIA ARITMETICA; COMPUTOS INFINITOS; MAQUINA DE TURING; MAQUINA MONOTONA; K-TRIVIALIDAD; NOCION DE LOWNESS (BAJURA); TRACEABILITY (RASTREABILIDAD); NUMEROS ABSOLUTAMENTE NORMALES; ALGORITHMIC INFORMATION THEORY; COMPUTABILITY THEORY; PROGRAM-SIZE COMPLEXITY; KOLMOGOROV COMPLEXITY; NORMAL NUMBERS; ABSOLUTELY NORMAL NUMBERS; RANDOMNESS; CHAITIN'S OMEGA NUMBER; HALTING PROBABILITY; ARITHMETICAL HIERARCHY; INFINITE COMPUTATION; TURING MACHINE; MONOTONE MACHINE; K-TRIVIALITY; LOWNESS NOTION; TRACEABILITY; CHAITINÔÇÖS OMEGA NUMBER