¿Existe una teoría para responder "el programa más simple para resolver un problema"?

10

Para responder "qué problemas se pueden resolver con la informática", desarrollamos la teoría de la computabilidad. Para los problemas que son computables, ¿existe una teoría para responder la pregunta "¿Es el programa el que obtengo más simple"?

No creo que la complejidad computacional responda la pregunta. Creo que considera cuánto tiempo necesitamos (aunque medido de manera abstracta).

No estoy seguro de si la teoría algorítmica de la información responde a la pregunta. Parece que la teoría habla sobre el tamaño, donde la equivalencia de tamaño mínimo y más simple no es obvia para mí (bueno, al menos se sienten diferentes para mí).

Creo que la teoría debería al menos definir la relación "simple" o "más simple que".


Ahora estoy convencido de que debería analizar la complejidad de Kolmogorov. Sin embargo, me gustaría explicar lo que tenía en mente cuando hacía la pregunta.

Cuando mejoro un programa, trato de reducir las conexiones innecesarias entre diferentes partes del programa (tal vez volver a dividir las partes para que pueda haber conexiones menos o más débiles). Como las conexiones se reducen, el programa se siente "más simple". De ahí la elección de la palabra "simple" cuando estoy formulando la pregunta. Es muy probable que el tamaño del programa también disminuya, pero ese es un buen efecto secundario, no el objetivo principal. Obviamente, el proceso de mejora no puede durar para siempre. Hay un punto que debería parar. Si, solo considerando la "estructura" (perdón por otro concepto indefinido) o "relación", ¿puedo convencerme de que no se puede hacer nada más?

Aquí contiene una mejor descripción de mi noción de complejidad.

Olaf Sporns (2007) Complejidad . Scholarpedia , 2 (10): 1623

Yuning
fuente
44
Quizás te interese el concepto de profundidad lógica de Bennett. Li y Vitanyi le han dedicado el capítulo 7.7 en su libro sobre la complejidad de Kolmogorov.
Martin Schwarz el
2
@YuNing: ¿Qué quieres decir con "más simple", si no con el tamaño?
Rob
1
@Yu Ning: ¿Qué tal, en lugar de que el programa más pequeño sea el más pequeño para producir una salida, es la máquina Turing con la mejor longitud mínima de descripción, de modo que haya un equilibrio entre 'pequeña' y 'estructura'?
Ross Snider
3
Creo que la pregunta está un poco mal definida. También tenga en cuenta que hay algoritmos que son muy simples, pero es difícil demostrar que son correctos. Y hay algoritmos que son simples y claramente correctos, pero es difícil demostrar que son rápidos.
Jukka Suomela

Respuestas:

16

Este problema se estudia en la teoría de la información algorítmica. Lo que estás definiendo se llama complejidad de Kolmogorov-Chaitin.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

Y parece que la noción de simplicidad que necesita puede formalizarse mediante la noción de medida de complejidad, que se formaliza mediante los axiomas de Blum.

http://en.wikipedia.org/wiki/Blum_axioms

Parece también que es posible generalizar la complejidad de Kolmogorov para tener en cuenta otras medidas de complejidad. Ver referencia a continuación. (El artículo de Wikipedia sobre la complejidad de Kolmogorov aborda este problema).

Burgin1990- Complejidad de kolmogorov generalizada y otras medidas de complejidad dual Análisis cibernético y de sistemas Volumen 26, número 4, 481-490

Mateus de Oliveira Oliveira
fuente
Como dice @Jukka Suomela, la pregunta está un poco mal definida. Por lo tanto, me pregunto que difícilmente puedo obtener una respuesta completa para la pregunta. Sin embargo, dado que esta respuesta es bastante informativa y toca una parte importante de la pregunta, todavía la etiqueto como la respuesta.
Yuning
Por cierto, ¿puede indicarme más sobre la aplicación del tema, específicamente si uno tiene una especificación formal de un programa, puede encontrar el tamaño más pequeño de la especificación?
Yuning
1

La respuesta para la primera pregunta es Sí, hay una teoría, es una teoría de información algorítmica y se llaman programas elegantes (por Gregory Chaitin).

Para la segunda pregunta sobre "¿es el programa que obtengo el más simple"?

No hay respuesta , porque es una pregunta incontestable, no es posible demostrar que un programa es un programa Elegante.

He puesto una respuesta para agregar la mención sobre programas elegantes .

Hernán Eche
fuente
-1

Hay diferentes tipos de enfoque para decidir qué es un código simple y qué no.

Pero lamentablemente, no hay una forma automática de determinarlo, por ejemplo, la complejidad de Kolmogorov falla con las funciones recursivas, algunas funciones recursivas (lógica profunda) son simples, pero la comprensión al respecto no es tan simple.

En mi experiencia, nuestro equipo estaba trabajando en un sistema y encontramos un procedimiento "simple" en Oracle (no más de 50 líneas) ... e intentamos entenderlo, nos llevó 2 meses (y varias reuniones) comprenderlo completamente. no por la complejidad del código sino por la lógica detrás de cada variable.

Creo que la forma de determinar qué tan simple es un código es: "leer un código y considerar el tiempo utilizado para comprenderlo".

Entonces, "¿El programa más simple para resolver un problema?" se puede dividir en:

a) simplicidad del código (código claro) pero es demasiado subjetivo.

b) sobrecomplejidad de la función, si tengo un problema X, entonces debo resolver la tarea DX (Delta X) para resolverlo, donde DX debe tender a X.

Por ejemplo, si mi problema es (uno) "pelar una manzana" y debo hacerlo en PHP (y lenguaje), entonces

si soy extremadamente afortunado y PHP tiene la función function_peel_apple (), entonces es el código más simple jamás X = 1 DX = 1, ¡simplemente llame a la función y listo!

Por el contrario, si no soy tan afortunado pero existe la función function_peel () y function_get_apple (), entonces X = 1 (un problema) y DX = 2 (dos tareas).

Si, en el peor de los casos, no existe ninguna función, entonces debo crear una (o más de una) por mí mismo y agregar varias tareas antes de resolver el problema, ahora ese es un programa complejo.


fuente