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
Respuestas:
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
fuente
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 .
fuente
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