Algoritmos poderosos que são muito difíceis de implementar - como ter certeza de que estão certos?

9

Estou me referindo à pergunta aqui: algoritmos poderosos complexos demais para serem implementados .

Se um algoritmo é poderoso, mas complexo demais para implementar, como você pode ter certeza de que o algoritmo está correto? Sem implementação, você não poderá testar o algoritmo em um cenário do mundo real, e um algoritmo tão complexo pode conter bugs, o que pode invalidar o algoritmo.

Isto é o que eu não entendo; se você possui as técnicas para provar a correção de um algoritmo, já teria o algoritmo para implementá-lo, não é? Ou então, como podemos ter certeza de que a técnica de prova está correta?

Me desculpe se pareço elementar!

Atualização do Kaveh (reproduzida aqui porque o argumento é melhor!):

Se você pode provar formalmente a correção de um algoritmo em um sistema formal como o Coq, também pode extrair o algoritmo (porque essencialmente você implementou o algoritmo), mas o fato principal é que, para a maioria dos algoritmos, não fornecemos provas formais de correção do algoritmo, usamos provas informais de correção. As provas podem ser falsas, o que acontece de tempos em tempos, e mesmo uma prova formal de correção não nos garante a certeza absoluta de que o algoritmo está correto.

ds.algorithms implementation Graviton
fonte
6
É por isso que temos técnicas para provar a exatidão dos algoritmos, mesmo que a implementação (correta) em uma máquina real seja difícil.
Raphael
9
Eu concordo com o Raphael. Parece que a pergunta se baseia na suposição de que a correção de um algoritmo geralmente é comprovada pela implementação, mas não é o caso. Provar a correção de um algoritmo e implementá-lo são coisas completamente diferentes, e uma coisa não implica a outra em nenhuma direção.
Tsuyoshi Ito 24/01
8
Algoritmos simples com provas complexas de correção - como você sabe que eles estão certos? Só porque um algoritmo funciona em exemplos de teste não significa que ele funciona em todas as entradas.
quer
2
Concordo com a maioria dos comentários, mas acho que eles estão perdendo um ponto-chave. Se você pode provar formalmente a correção de um algoritmo em um sistema formal como o Coq, também pode extrair o algoritmo (porque essencialmente você implementou o algoritmo), mas o fato principal é que, para a maioria dos algoritmos , não fornecemos provas formais de correção do algoritmo, usamos provas informais de correção. As provas podem ser falsas, isso acontece de tempos em tempos, e mesmo uma prova formal de correção não nos garante a certeza absoluta de que o algoritmo está correto.
Kaveh
5
"Cuidado com os bugs no código acima; eu apenas provei que está correto, não tentei." ~ Donald Knuth
Lev Reyzin

Respostas:

11

Há vários anos, houve um debate (bastante severo) sobre um tópico semelhante a este. Tudo começou quando várias provas complexas se mostraram incorretas e alguns pesquisadores começaram a levantar dúvidas sobre a própria natureza das provas (bem, eu deveria ter dito "criptografia comprovável", mas por uma questão de generalidade, não o fiz). . Ambos os lados da controvérsia acusaram o outro de interpretar mal os conceitos. Aqui está um link para mais informações .

As provas são nossas ferramentas (matemáticas) para provar que os teoremas / algoritmos estão corretos, mas quando se tornaram muito complexos, podemos escapar e provar que as coisas erradas estão certas. A recente prova de cerca de 100 páginas no P ≠ NP é um excelente exemplo. No entanto, isso não descarta a própria natureza das provas: não há nada errado com elas.

Um último ponto: acho que estudar o filosofia da ciência nos dará mais informações sobre isso. (No link fornecido, consulte o marcador " Como sabemos se uma prova matemática está correta? ")

MS Dousti
fonte