Bueno, lo que sabemos es que la cadena generada por la secuencia más corta se puede generar utilizando el patrón y un programa para ejecutar el patrón para una cierta cantidad de pasos (m). Del mismo modo, el más largo podría generarse con el mismo patrón y el mismo programa, y usando n pasos (presumiblemente, n> m). Entonces, el peor de los casos es que cada uno requiere la longitud del patrón más la longitud de la “máquina iteradora” más el registro de n o m.
Este es el corazón de la respuesta de Jonathan Paulsen, y es un punto de partida válido.
Sin embargo, es posible que cualquiera de las cadenas generadas también pueda generarse mediante algoritmos más simples. Entonces, tenemos un límite superior para sus complejidades de Kolmogorov, pero no tenemos un límite inferior. De hecho, la cadena generada por el patrón pero que requiere más pasos en ese patrón, en realidad puede tener una complejidad general * más pequeña * porque podría ser una forma más sencilla de generarlo que usar el patrón proporcionado.
- ¿Qué es un algoritmo? ¿Es simplemente una máquina de Turing? Si no, ¿qué es?
- Dada una matriz 2D de valores booleanos, ¿cuál es la forma correcta de determinar si contiene un triángulo?
- Cómo encontrar la longitud máxima de la cadena que forma palíndromo en Java
- ¿Cuál es el mejor lenguaje para implementar estructuras y algoritmos de datos fundamentales?
- ¿Cómo se conocen entre sí los procesos en un sistema distribuido?
