Conjunto K-trivial

Tipo de conjunto en matemáticas

En matemáticas , un conjunto de números naturales se denomina conjunto K-trivial si sus segmentos iniciales vistos como cadenas binarias son fáciles de describir: la complejidad de Kolmogorov sin prefijos es lo más baja posible, cercana a la de un conjunto computable . Solovay demostró en 1975 que un conjunto puede ser K-trivial sin ser computable.

El teorema de Schnorr-Levin dice que los conjuntos aleatorios tienen una alta complejidad de segmento inicial. Por tanto, los K-triviales están lejos de ser aleatorios. Es por ello que estos conjuntos se estudian en el campo de la aleatoriedad algorítmica , que es un subcampo de la teoría de la Computabilidad y relacionado con la teoría algorítmica de la información en informática .

Al mismo tiempo, los conjuntos K-triviales son casi computables. Por ejemplo, todos son superbajos, es decir, conjuntos cuyo salto de Turing es computable a partir del problema de detención , y forman un ideal de Turing, es decir, una clase de conjuntos cerrados bajo la unión de Turing y cerrados hacia abajo bajo la reducción de Turing .

Definición

Sea K la complejidad de Kolmogorov sin prefijo , es decir, dada una cadena x, K(x) genera la longitud mínima de la cadena de entrada en una máquina universal sin prefijo . Una máquina así, intuitivamente, representa un lenguaje de programación universal con la propiedad de que ningún programa válido puede obtenerse como una extensión adecuada de otro programa válido. Para obtener más información sobre K, consulte, por ejemplo, la constante de Chaitin .

Decimos que un conjunto A de números naturales es K-trivial mediante una constante b ∈ si ${\displaystyle \mathbb {N} }$

${\displaystyle \forall nK(A\upharpoonright n)\leq K(n)+b}$.

Un conjunto es K-trivial si es K-trivial mediante alguna constante. ^{[1] [2]}

Breve historia y desarrollo.

En los primeros días del desarrollo de la K-trivialidad, se prestó atención a la separación de los conjuntos K-triviales y los conjuntos computables .

Chaitin en su artículo de 1976 ^[3] estudió principalmente conjuntos tales que existe b ∈ con ${\displaystyle \mathbb {N} }$

${\displaystyle \forall nC(A\upharpoonright n)\leq C(n)+b}$

donde C denota la complejidad simple de Kolmogorov . Estos conjuntos se conocen como conjuntos C-triviales. Chaitin demostró que coinciden con los conjuntos computables. También demostró que los K-triviales son computables en el problema de detención . Esta clase de conjuntos se conoce comúnmente como conjuntos en jerarquía aritmética . ${\displaystyle \Delta _{2}^{0}}$

Robert M. Solovay fue el primero en construir un conjunto K-trivial no computable, mientras que Calude , Coles ^[4] y otras construcciones inéditas de Kummer de un K-trivial y Muchnik junior de un K-trivial intentaron construir un A computablemente enumerable. bajo para el conjunto K.

Desarrollos 1999-2008

En el contexto de la teoría de la computabilidad, una función de costos es una función computable

${\displaystyle c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}.}$

Para una aproximación computable del conjunto A , dicha función mide el costo c ( n , s ) de cambiar la aproximación a A(n) en la etapa s. La primera construcción de la función de costes se debió a Kučera y Terwijn. ^[5] Construyeron un conjunto computable enumerable que es bajo para la aleatoriedad de Martin-Löf pero no computable. Su función de costos era adaptativa, en el sentido de que la definición de la función de costos depende de la aproximación computable del conjunto que se está construyendo. ${\displaystyle \langle A_{s}\rangle }$ ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$

Una construcción de función de costos de un conjunto K-trivial computable, enumerable y no computable apareció por primera vez en Downey et al. ^[6]

Decimos que un conjunto A obedece a una función de costos c si existe una aproximación computable de A, ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \langle A_{s}:s\in \omega \rangle }$ ${\displaystyle S=\Sigma _{x,s}c(x,s)[x<s\wedge {\text{x is the least s.t. }}A_{s-1}(x)\neq A_{s}(x)]<\infty .}$

Los conjuntos K-triviales se caracterizan ^[7] por la obediencia a la función de costo estándar, definida por

${\displaystyle c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}}$dónde ${\displaystyle K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}}$

y es el s -ésimo paso en una aproximación computable de una máquina fija universal sin prefijo . ${\displaystyle \mathbb {U} _{s}}$ ${\displaystyle \mathbb {U} }$

Bosquejo de la construcción de un conjunto K-trivial no computable

De hecho, el conjunto se puede simplificar rápidamente. La idea es cumplir con los requisitos de simplicidad inmediata,

${\displaystyle PS_{e}:|W_{e}|=\infty \Rightarrow \exists s\exists x[x\in W_{e,s}\backslash W_{e,s-1}\wedge x\in A_{s}]}$

así como para mantener los costos bajos. Necesitamos la función de costo para satisfacer la condición límite.

${\displaystyle \lim _{x}\sup _{s>x}c(x,s)=0}$

es decir, el supremo sobre las etapas del costo de x llega a 0 a medida que x aumenta. Por ejemplo, la función de costo estándar tiene esta propiedad. Básicamente, la construcción espera hasta que el costo sea bajo antes de hacer números para cumplir con los requisitos inmediatamente simples. Definimos una enumeración computable tal que ${\displaystyle A}$ ${\displaystyle \langle A_{s}:s\in \omega \rangle }$

${\displaystyle A_{0}=\emptyset }$. En la etapa s > 0 , para cada e  <  s , si aún no se ha cumplido y existe x  ≥ 2 e tal que y , entonces colocamos x y declaramos que se cumple. Fin de la construcción. ${\displaystyle PS_{e}}$ ${\displaystyle x\in W_{e,s}\backslash W_{e,s-1}}$ ${\displaystyle c(x,s)\leq 2^{-e}}$ ${\displaystyle A_{s}}$ ${\displaystyle PS_{e}}$

Para verificar que la construcción funciona, observe primero que A obedece a la función de costos ya que como máximo un número ingresa a A por cada requerimiento. Por lo tanto, la suma S es como máximo

${\displaystyle \Sigma _{e}2^{-e}<\infty .}$

En segundo lugar, se cumple cada requisito: si es infinito, por el hecho de que la función de costos satisface la condición límite, eventualmente se enumerará algún número en A para cumplir el requisito. ${\displaystyle W_{e}}$

Caracterizaciones equivalentes

La K-trivialidad resulta coincidir con algunas nociones de bajeza computacional, que dicen que un conjunto es casi computable. Las siguientes nociones capturan la misma clase de conjuntos. ^[7]

Humildad parak

Decimos que A es bajo para K si existe b ∈ tal que ${\displaystyle \mathbb {N} }$

${\displaystyle \forall nK^{A}(n)+b\geq K(n).}$

Aquí se muestra la complejidad de Kolmogorov sin prefijos en relación con Oracle . ${\displaystyle K^{A}}$ ${\displaystyle A}$

Lowness para la aleatoriedad de Martin-Löf

A es bajo para la aleatoriedad de Martin-Löf [ ^8] si siempre que Z es aleatorio de Martin-Löf , ya es aleatorio de Martin-Löf en relación con A.

Base para la aleatoriedad de Martin-Löf

A es una base para la aleatoriedad de Martin-Löf si A es reducible por Turing a Z para algún conjunto Z que es aleatorio de Martin-Löf en relación con A. ^[7]

Se han estudiado caracterizaciones más equivalentes de K-trivialidad, como:

1. Bajada por aleatoriedad débil-2;
2. Lowness para reales de diferencia-izquierda-ce (obsérvese que aquí no se menciona aleatoriedad).

Acontecimientos después de 2008

A partir de 2009 entraron en escena conceptos provenientes del análisis. Esto ayudó a resolver algunos problemas notorios.

Se dice que un conjunto Y es un punto de densidad positivo si cada clase efectivamente cerrada que contiene Y tiene una densidad de Lebesgue inferior positiva en Y. Bienvenu, Hölzl, Miller y Nies ^[9] demostraron que un ML-aleatorio es Turing incompleto si es un punto de densidad positiva. Day y Miller ^[10] usaron esto para una respuesta afirmativa al problema de la ventosa ML: ^[11] A es K-trivial si y solo para cada conjunto aleatorio Z de Martin-Löf tal que A⊕Z calcula el problema de detención , ya Z por sí mismo Calcula el problema de detención .

Se dice que un conjunto Y es un punto de densidad-un punto si cada clase efectivamente cerrada que contiene Y tiene una densidad de Lebesgue 1 en Y. Cualquier conjunto aleatorio de Martin-Löf que no sea un punto de densidad-un calcula cada conjunto K trivial de Bienvenu, et al. . ^[12] Day y Miller demostraron que existe un conjunto aleatorio de Martin-Löf que es un punto de densidad positivo pero no un punto de densidad. Por tanto, existe un conjunto aleatorio de Martin-Löf incompleto que calcula cada conjunto K-trivial. Esto respondió afirmativamente al problema de cobertura planteado primero por Stephan y luego publicado por Miller y Nies. ^[13] Para un resumen, ver L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies y D. Turetsky. ^[14]

Se han estudiado variantes de K-trivialidad:

• Conjuntos triviales de Schnorr donde las máquinas tienen dominio con medida computable.
• salta fuertemente conjuntos trazables, una propiedad de bajeza de conjuntos muy dentro de la K-trivialidad.

Referencias

1. A. Nies (2009). Computabilidad y aleatoriedad, Publicaciones científicas de Oxford, ISBN  978-0199230761
2. Downey, Rodney G., Hirschfeldt, Denis R. (2010), "Aleatoriedad y complejidad algorítmica", ISBN 978-0-387-68441-3 
3. Gregory J. Chaitin (1976), "Caracterizaciones teóricas de la información de cadenas infinitas recursivas", Ciencias de la Computación Teórica Volumen 2, Número 1, junio de 1976, páginas 45–48
4. Cristian Calude, Richard J. Coles, Complejidad del tamaño del programa de segmentos iniciales y reducibilidad de dominación, (1999), procedencia de: Las joyas son para siempre, contribuciones a la informática teórica en honor a Arto Salomaa
5. Antonin Kučera y Sebastiaan A. Terwijn (1999), "Bajada para la clase de conjuntos aleatorios", The Journal of Symbolic Logic vol. 64, núm. 4 (diciembre de 1999), págs. 1396-1402
6. Rod G. Downey, Denis R. Hirschfeldt, Andr ́e Nies, Frank Stephan, "Trivial Reals", Electronic Notes in Theoretical Computer Science 66 No. 1 (2002), URL: "Elsevier.nl - de pagina kan niet worden weergegeven ". Archivado desde el original el 3 de octubre de 2005 . Consultado el 3 de enero de 2014 .
7. André Nies, (2005), "Propiedades de bajeza y aleatoriedad", Avances en matemáticas , volumen 197, número 1, 20 de octubre de 2005, páginas 274–305
8. Antonin Kučera y Sebastiaan A. Terwijn (1999), "Bajada para la clase de conjuntos aleatorios", The Journal of Symbolic Logic , vol. 64, núm. 4 (diciembre de 1999), págs. 1396-1402
9. Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller y André Nies, (2012), "La alternativa Denjoy para funciones computables", Actas del 29º Simposio internacional sobre aspectos teóricos de la informática (STACS 2012), volumen 14 de Leibniz Procedimientos internacionales en informática, páginas 543–554. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2012.
10. J. Miller, A. Día. (2012) "Ahuecamiento con conjuntos aleatorios", que aparecerá en las actas de la American Mathematical Society
11. Miller y Nies, Aleatoriedad y computabilidad: preguntas abiertas. Toro. Símb. Lógica. 12 nº 3 (2006) 390-410
12. Bienvenu, Greenberg, Kucera, Nies y Turetsky, "K-Triviality, Oberwolfach Randomness y Diferenciabilidad", Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach Preprints (OWP), ISSN  1864-7596
13. Miller y Nies, Aleatoriedad y computabilidad: preguntas abiertas. Toro. Símb. Lógica. 12 nº 3 (2006) 390–410
14. Calcular conjuntos K-triviales mediante conjuntos aleatorios incompletos. Toro. Lógica simbólica. 20, marzo de 2014, págs. 80-90.