Para las complejidades de Kolmogorov inducida por lenguajes de descripción esencialmente óptimos,
¿existe un entero c tal que para todos los enteros positivos n ,
exista una cadena x tal que
?
A diferencia de la pregunta que me inspiró , la respuesta de esta pregunta es sólida frente a la elección de, ya que por definición es un "lenguaje de descripción esencialmente óptimo" si y solo si
es una función parcial computable de{
a sí mismo de modo que para todas
las funciones parciales computables L
de{ para sí mismo, existe un
enterocy una función computable (total)
tal que
para todas las cadenas , y .
kolmogorov-complexity
Comunidad
fuente
fuente
Respuestas:
fuente