Conjunto k-trivial

Tipos de conjuntos 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 prefijo 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 lo tanto, los K-triviales están lejos de ser aleatorios. Por eso, estos conjuntos se estudian en el campo de la aleatoriedad algorítmica , que es un subcampo de la teoría de la computabilidad y está relacionado con la teoría de la información algorítmica en la informática .

Al mismo tiempo, los conjuntos K-triviales están cerca de ser computables. Por ejemplo, todos son superbajos, es decir, conjuntos cuyo salto de Turing es computable a partir del problema de Halting , 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 bajo una máquina universal sin prefijo . Dicha máquina, intuitivamente, representa un lenguaje de programación universal con la propiedad de que no se puede obtener ningún programa válido como extensión propia 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 a través de 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 conjuntos K-triviales y 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 de Kolmogorov simple . 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 la construcción de un conjunto A computablemente enumerable fue intentada por Calude , Coles ^[4] y otras construcciones inéditas de Kummer de un K-trivial, y Muchnik junior de un conjunto bajo para K.

Evolución 1999-2008

En el contexto de la teoría de computabilidad, una función de costo 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 costo se debió a Kučera y Terwijn. ^[5] Construyeron un conjunto computablemente enumerable que es bajo para la aleatoriedad de Martin-Löf pero no computable. Su función de costo fue adaptativa, en el sentido de que la definición de la función de costo 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 costo de un conjunto no computable computablemente enumerable K-trivial apareció por primera vez en Downey et al. ^{[6] .}

Decimos que un conjunto A obedece a una función de costo 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 paso s -ésimo en una aproximación computable de una máquina universal fija sin prefijos . ${\displaystyle \mathbb {U} _{s}}$ ${\displaystyle \mathbb {U} }$

Esquema 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 rápida.

${\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 que la función de costos satisfaga la condición límite.

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

es decir, el supremo sobre las etapas del costo para x tiende a 0 a medida que x aumenta. Por ejemplo, la función de costo estándar tiene esta propiedad. La construcción esencialmente espera hasta que el costo sea bajo antes de colocar números para cumplir con los requisitos simples inmediatos. 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 ponemos x en 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 comprobar que la construcción funciona, observe primero que A obedece a la función de costo, ya que, como máximo, entra un número en A por cada requisito. 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 costo satisface la condición límite, algún número eventualmente se enumerará en A para cumplir el requisito. ${\displaystyle W_{e}}$

Caracterizaciones equivalentes

Resulta que la k-trivialidad coincide con algunas nociones de lentitud computacional, que dicen que un conjunto es cercano a computable. Las siguientes nociones capturan la misma clase de conjuntos. ^[7]

Bajeza paraK

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

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

Aquí se muestra la complejidad de Kolmogorov sin prefijo relativa al oráculo . ${\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 aleatoria de Martin-Löf , ya es aleatoria 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 la K-trivialidad, tales como:

1. Bajeza por aleatoriedad débil-2;
2. Bajeza para reales de diferencia-izquierda-ce (nótese que aquí no se menciona aleatoriedad).

Evolución posterior a 2008

A partir de 2009, los conceptos de análisis entraron en escena, lo que 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. Bienvenido, Hölzl, Miller y Nies ^[9] demostraron que un ML-aleatorio es Turing incompleto si y solo si es un punto de densidad positivo. Day y Miller ^[10] usaron esto para una respuesta afirmativa al problema de ML-cupping: ^[11] A es K-trivial si y solo si para cada conjunto aleatorio de Martin-Löf Z tal que A⊕Z calcula el problema de detención , ya que Z por sí mismo calcula el problema de detención .

Se dice que un conjunto Y es un punto de densidad uno si cada clase efectivamente cerrada que contiene a Y tiene densidad de Lebesgue 1 en Y. Cualquier conjunto aleatorio de Martin-Löf que no sea un punto de densidad uno calcula cada conjunto trivial K por 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 uno. Por lo tanto, existe un conjunto aleatorio de Martin-Löf incompleto que calcula cada conjunto trivial K. Esto respondió afirmativamente al problema de cubrimiento planteado primero por Stephan y luego publicado por Miller y Nies. ^[13] Para un resumen, véase L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies y D. Turetsky. ^[14]

Se han estudiado variantes de la K-trivialidad:

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

Referencias

1. A. Nies (2009). Computabilidad y aleatoriedad, Oxford Science Publications, ISBN  978-0199230761
2. Downey, Rodney G., Hirschfeldt, Denis R. (2010), "Aleatoriedad y complejidad algorítmicas", ISBN 978-0-387-68441-3 
3. Gregory J. Chaitin (1976), "Caracterizaciones teóricas de la información de cadenas infinitas recursivas", Theoretical Computer Science, 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), procedimiento de: Las joyas son eternas, contribuciones a la informática teórica en honor a Arto Salomaa
5. Antonin Kučera y Sebastiaan A. Terwijn (1999), "Lowness para la clase de conjuntos aleatorios", The Journal of Symbolic Logic Vol. 64, No. 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 baja estatura y aleatoriedad", Advances in Mathematics , Volumen 197, Número 1, 20 de octubre de 2005, páginas 274–305
8. Antonin Kučera y Sebastiaan A. Terwijn (1999), "Lowness para la clase de conjuntos aleatorios", The Journal of Symbolic Logic , vol. 64, n.º 4 (diciembre de 1999), págs. 1396-1402
9. Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller y André Nies, (2012), "La alternativa de Denjoy para funciones computables", Actas del 29.° Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2012), volumen 14 de Leibniz International Proceedings in Informatics, páginas 543-554. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.
10. J. Miller, A. Day. (2012) "Cupping with random sets", que aparecerá en las Actas de la Sociedad Americana de Matemáticas
11. Miller y Nies, Aleatoriedad y computabilidad: preguntas abiertas. Bull. Symb. Logic. 12 no 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. Bull. Symb. Logic. 12 no 3 (2006) 390–410
14. Cálculo de conjuntos K-triviales mediante conjuntos aleatorios incompletos. Bull. Symbolic Logic. 20, marzo de 2014, págs. 80-90.