Para responder "que problemas podem ser resolvidos pela computação", desenvolvemos a teoria da computabilidade. Para os problemas computáveis, existe uma teoria para responder à pergunta "o programa é o mais simples?"?
Não acho que a complexidade computacional responda à pergunta. Eu acho que considera quanto tempo precisamos (embora medidos abstratamente).
Não tenho certeza se a teoria algorítmica da informação responde à pergunta. Parece que a teoria fala sobre tamanho, onde a equivalência entre tamanho mínimo e mais simples não é óbvia para mim (bem, pelo menos eles se sentem diferentes para mim).
Eu acho que a teoria deveria pelo menos definir a relação "simples" ou "mais simples que".
Agora estou convencido de que devo examinar a Complexidade de Kolmogorov. No entanto, gostaria de explicar o que estava em minha mente quando estava fazendo a pergunta.
Quando aprimoro um programa, tento reduzir as conexões desnecessárias entre diferentes partes do programa (talvez re-dividindo as partes para que haja conexões menores ou mais fracas). Como as conexões são reduzidas, o programa parece "mais simples". Daí a escolha da palavra "simples" quando estou formulando a pergunta. É muito provável que o tamanho do programa também diminua, mas esse é um bom efeito colateral, não o objetivo principal. Obviamente, o processo de melhoria não pode durar para sempre. Há um ponto em que devo parar. Se, apenas considerando a "estrutura" (desculpe por outro conceito indefinido) ou "relação", posso me convencer de que nada mais pode ser feito?
Aqui contém uma descrição melhor da minha noção de complexidade.
Olaf Sporns (2007) Complexidade . Scholarpedia , 2 (10): 1623
Respostas:
Este problema é estudado na teoria algorítmica da informação. O que você está definindo é chamado complexidade Kolmogorov-Chaitin.
http://en.wikipedia.org/wiki/Kolmogorov_complexity
E parece que a noção de simplicidade exigida pode ser formalizada através da noção de medida de complexidade, formalizada pelos axiomas de Blum.
http://en.wikipedia.org/wiki/Blum_axioms
Parece também que é possível generalizar a complexidade de Kolmogorov para levar em consideração outras medidas de complexidade. Veja a referência abaixo. (O artigo da Wikipedia sobre a complexidade de Kolmogorov aborda esse problema.)
Burgin1990- Complexidade generalizada de kolmogorov e outras medidas de dupla complexidade Cibernética e Análise de Sistemas Volume 26, Número 4, 481-490
fonte
A resposta para a primeira pergunta é Sim, existe uma teoria, é a teoria da informação algorítmica e esses são chamados de Programas Elegantes (por Gregory Chaitin).
Para a segunda pergunta sobre "o programa é o mais simples"?
Não há resposta , porque é uma pergunta incontestável, não é possível provar que um programa é um programa elegante.
Eu coloquei uma resposta para adicionar a menção sobre programas elegantes .
fonte
Existem diferentes tipos de abordagem para decidir o que é um código simples e o que não é.
Mas, infelizmente, não há uma maneira automática de determiná-lo, por exemplo, a Complexidade de Kolmogorov falha com funções recursivas, algumas funções recursivas (profundidade lógica) são simples, mas o entendimento sobre ela não é tão simples.
Na minha experiência, nossa equipe estava trabalhando em um sistema e encontramos um procedimento "simples" no Oracle (não mais que 50 linhas) ... e tentamos entendê-lo, foram necessários 2 meses (e várias reuniões) para entender completamente não pela complexidade do código, mas pela lógica por trás de cada variável.
Penso que a maneira de determinar quão simples é um código é: "leia um código e considere o tempo usado para entendê-lo".
Então "O programa mais simples para resolver um problema?" pode ser dividido em:
a) simplicidade do código (código claro), mas é muito subjetivo.
b) supercomplexidade da função, se eu tiver um problema com X, devo resolver a tarefa do DX (Delta X) para resolvê-lo, onde o DX deve tender para o X.
Por exemplo, se meu problema for (um) "descascar uma maçã" e eu devo fazê-lo em PHP (e linguagem), então
se eu sou extremamente sortudo e o PHP tem a função function_peel_apple (), então é o código mais simples de todos os tempos X = 1 DX = 1, basta chamar a função e é isso !.
Por outro lado, se eu não tiver tanta sorte, mas existir a função function_peel () e function_get_apple (), então X = 1 (um problema) e DX = 2 (duas tarefas).
Se, na pior das hipóteses, não existir nenhuma função, eu devo criar uma (ou mais de uma) por mim e adicionar várias tarefas antes de resolver o problema, agora esse é um programa complexo.
fonte