Sobre la entropía algorítmica de objetos abstractos

Mostrar todas las versiones(3)

En la década de 1960 Gregory Chaitin desarrolló una teoría de complejidad (teoría de largo de programa, íntimamente emparentada con la noción de complejidad ideada por Andrei Kolmogorov) para las palabras, y demostró que esta noción puede ser interpretada como una medida de cantidad de información o...

Descripción completa

Detalles Bibliográficos
Autor principal: Moscato, Mariano Miguel
Formato: Tesis de Grado
Lenguaje:Español
Publicado: 22 J
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000452_Moscato
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:seminario_nCOM000452_Moscato
record_format dspace
spelling todo:seminario_nCOM000452_Moscato2023-10-03T16:48:35Z Sobre la entropía algorítmica de objetos abstractos Moscato, Mariano Miguel En la década de 1960 Gregory Chaitin desarrolló una teoría de complejidad (teoría de largo de programa, íntimamente emparentada con la noción de complejidad ideada por Andrei Kolmogorov) para las palabras, y demostró que esta noción puede ser interpretada como una medida de cantidad de información o entropía algorítmica. El sentido de entropía al que se refiere Chaitin es precisamente el dado por Claude Shannon en 1948 que, motivado por el problema de transmitir información eficientemente sobre un canal de comunicación, creó una nueva manera probabilística de pensar las comunicaciones y creo una teoría matemática de la entropía. Esta tesis tiene tres aportes fundamentales. En primer lugar ha sido un estudio detallado de uno de los trabajos menos conocidos y menos citados de Gregory Chaitin [2]. En este trabajo Chaitin define y estudia la entropía de conjuntos recursivamente enumerables. En esta tesis hemos conseguido una reescritura de sus teoremas fundamentales. El segundo aporte se vincula con la pregunta ¿hasta qué punto podemos hablar de la función de complejidad como medida de entropía en universos arbitrarios? El Teorema 5 da condiciones suficientes para esto: pide que exista una función que mapea palabras con elementos de un universo dado, y da condiciones suficientes sobre este mapeo para que la función de complejidad sobre este universo coincida con la de entropía. Y en particular, el Teorema 27 demuestra que el universo de los conjuntos finitos de números naturales (bajo cómputos finitos) admite esta noción de complejidad. Justamente la estrategia usada en esta tesis para demostrarlo se basa en la existencia de un mapeo entre las palabras y los conjuntos finitos que cumple con las condiciones suficientes dadas en el Teorema 5. En el citado trabajo de Chaitin se demuestra que, en general, la noción de complejidad no coincide con la de entropía para conjuntos recursivamente enumerables, excepto para clases particulares de conjuntos. El tercer aporte de esta tesis son dos nuevos teoremas que extienden los de Chaitin, para otra clases de conjuntos. Son los Teoremas 58 y 75. Fil: Moscato, Mariano Miguel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 22 Junio 2005 Tesis de Grado PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000452_Moscato
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
description En la década de 1960 Gregory Chaitin desarrolló una teoría de complejidad (teoría de largo de programa, íntimamente emparentada con la noción de complejidad ideada por Andrei Kolmogorov) para las palabras, y demostró que esta noción puede ser interpretada como una medida de cantidad de información o entropía algorítmica. El sentido de entropía al que se refiere Chaitin es precisamente el dado por Claude Shannon en 1948 que, motivado por el problema de transmitir información eficientemente sobre un canal de comunicación, creó una nueva manera probabilística de pensar las comunicaciones y creo una teoría matemática de la entropía. Esta tesis tiene tres aportes fundamentales. En primer lugar ha sido un estudio detallado de uno de los trabajos menos conocidos y menos citados de Gregory Chaitin [2]. En este trabajo Chaitin define y estudia la entropía de conjuntos recursivamente enumerables. En esta tesis hemos conseguido una reescritura de sus teoremas fundamentales. El segundo aporte se vincula con la pregunta ¿hasta qué punto podemos hablar de la función de complejidad como medida de entropía en universos arbitrarios? El Teorema 5 da condiciones suficientes para esto: pide que exista una función que mapea palabras con elementos de un universo dado, y da condiciones suficientes sobre este mapeo para que la función de complejidad sobre este universo coincida con la de entropía. Y en particular, el Teorema 27 demuestra que el universo de los conjuntos finitos de números naturales (bajo cómputos finitos) admite esta noción de complejidad. Justamente la estrategia usada en esta tesis para demostrarlo se basa en la existencia de un mapeo entre las palabras y los conjuntos finitos que cumple con las condiciones suficientes dadas en el Teorema 5. En el citado trabajo de Chaitin se demuestra que, en general, la noción de complejidad no coincide con la de entropía para conjuntos recursivamente enumerables, excepto para clases particulares de conjuntos. El tercer aporte de esta tesis son dos nuevos teoremas que extienden los de Chaitin, para otra clases de conjuntos. Son los Teoremas 58 y 75.
format Tesis de Grado
author Moscato, Mariano Miguel
spellingShingle Moscato, Mariano Miguel
Sobre la entropía algorítmica de objetos abstractos
author_facet Moscato, Mariano Miguel
author_sort Moscato, Mariano Miguel
title Sobre la entropía algorítmica de objetos abstractos
title_short Sobre la entropía algorítmica de objetos abstractos
title_full Sobre la entropía algorítmica de objetos abstractos
title_fullStr Sobre la entropía algorítmica de objetos abstractos
title_full_unstemmed Sobre la entropía algorítmica de objetos abstractos
title_sort sobre la entropía algorítmica de objetos abstractos
publishDate 22 J
url https://hdl.handle.net/20.500.12110/seminario_nCOM000452_Moscato
work_keys_str_mv AT moscatomarianomiguel sobrelaentropiaalgoritmicadeobjetosabstractos
_version_ 1807315968260571136

Ejemplares similares