Aspectos de aleatoriedad

Mostrar todas las versiones(3)

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...

Descripción completa

Detalles Bibliográficos
Autor principal:	Figueira, Santiago Daniel
Otros Autores:	Becher, Verónica Andrea
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Inglés
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2006
Materias:	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
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n3958_Figueira https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3958_Figueira_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-tesis_n3958_Figueira_oai
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Inglés
orig_language_str_mv	eng
topic	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
spellingShingle	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 Figueira, Santiago Daniel Aspectos de aleatoriedad
topic_facet	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
description	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.
author2	Becher, Verónica Andrea
author_facet	Becher, Verónica Andrea Figueira, Santiago Daniel
format	Tesis doctoral Tesis doctoral publishedVersion
author	Figueira, Santiago Daniel
author_sort	Figueira, Santiago Daniel
title	Aspectos de aleatoriedad
title_short	Aspectos de aleatoriedad
title_full	Aspectos de aleatoriedad
title_fullStr	Aspectos de aleatoriedad
title_full_unstemmed	Aspectos de aleatoriedad
title_sort	aspectos de aleatoriedad
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2006
url	https://hdl.handle.net/20.500.12110/tesis_n3958_Figueira https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3958_Figueira_oai
work_keys_str_mv	AT figueirasantiagodaniel aspectosdealeatoriedad AT figueirasantiagodaniel aspectsofrandomness
_version_	1824354927532572672
spelling	I28-R145-tesis_n3958_Figueira_oai2024-09-02 Becher, Verónica Andrea Figueira, Santiago Daniel 2006 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. In this thesis we investigate some aspects of randomness and triviality defined by the theory of program-size. We first deal with randomness and absolute normality of real numbers. Both sets of reals have Lebesgue measure 1 and they are notions that imply several properties of stochasticity. Despite that fact, it has not been easy to give concrete examples in such classes. We prove that there are absolutely normal numbers which are computable and we give two algorithms for constructing such numbers. The former is a computable reformulation of a result of Sierpinski of 1916. The latter is part of our reconstruction of an unpublished manuscript of Turing on normal numbers. For examples of randomness, we generalize Chaitin's halting probability and we analyze the probability that a universal machine halts and gives an output in a given set X. We study the relationship between the computability theoretic properties of X and the randomness properties of the induced probability. The second aspect of randomness that we tackle is the study a variant of the classical definition of program-size complexity which does not involve oracles, and we ask whether it leads to a stronger notion of randomness. We define our complexity function based on monotone Turing machines performing unending computations. We investigate some properties of this function and we consider the induced definitions of randomness and triviality. With this last notion we characterize the computable reals. The last aspect deals with anti-randomness and the possibility to characterize the so called K-trivial reals in terms of notions that do not directly involve the prefix-free program-size complexity. We propose and investigate two computability theoretical combinatorial lowness notions by strengthening other notions already existing in the literature. We relate the plain C and the prefix-free program-size complexity K with these notions by considering variations of K-triviality and C-triviality. We conclude with a list of the main questions that remain open. Fil: Figueira, Santiago Daniel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n3958_Figueira eng Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar 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 Aspectos de aleatoriedad Aspects of randomness info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3958_Figueira_oai

Aspectos de aleatoriedad

Ejemplares similares