Por que não pode ser provado programas?

https://stackoverflow.com/questions/476959

20-08-2019
|

Pergunta

Por que não um programa de computador ser provado apenas como uma lata enunciado matemático? A prova matemática é construída em outras provas, que são construídas a partir de ainda mais provas e para baixo, para axiomas -. Aquelas verdades verdades que nos são tão evidentes

programas

Computer não parecem ter uma estrutura deste tipo. Se você escrever um programa de computador, como é que você pode tirar obras comprovadas anteriores e usá-los para mostrar a verdade do seu programa? Você não pode uma vez que nenhum existir. Além disso, quais são os axiomas da programação? As verdades muito atômicas do campo?

Eu não tenho boas respostas para os itens acima. Mas parece software não pode ser provada, porque é arte e não ciência. Como você prova um Picasso?

Solução

são programas .

Verificação formal de programas é uma enorme área de pesquisa. (Ver, por exemplo, o grupo na Carnegie Mellon .)

Muitos programas complexos foram verificados; por exemplo, ver este núcleo escrito em Haskell .

Outras dicas

Programas absolutamente pode ser provado ser correto. programas ruins são difíceis de provar. Para fazê-lo, mesmo razoavelmente bem, você tem que desenvolver o programa e mão-na-mão a prova.

Você não pode automatizar a prova por causa do problema da parada. Você pode, no entanto, revelar-se manualmente as pós-condições e condições prévias de qualquer declaração arbitrária, ou uma sequência de declarações.

Você deve ler da Dijsktra A disciplina de Programação .

Em seguida, você deve ler Gries' A Ciência da Programação .

Em seguida, você vai saber como provar programas corrigir.

Apenas um pequeno comentário para aqueles que trouxe incompletude -. Não é o caso de todas sistemas axiomáticos, apenas a suficientemente poderoso as

Em outras palavras, Godel provou que um poderoso o suficiente sistema axiomático para descrever si seria necessariamente incompleta. Isso não quer dizer que seria inútil no entanto, e como já foi ligada a, várias tentativas de provas do programa foram feitas.

O problema dual (escrever programas para verificar provas) também é muito interessante.

Você pode, de facto escrever programas comprovadamente corretas. Microsoft, por exemplo, criou uma extensão da linguagem C # chamado Spec # que inclui um provador de teoremas automatizado. Para java, há ESC / java . Eu tenho certeza que existem muitos exemplos mais lá fora.

( Editar : aparentemente especificação # não está mais sendo desenvolvido, mas as ferramentas contrato se tornará parte do .NET 4.0 )

Eu vejo alguns cartazes mão-acenando sobre a parada problema ou incompletude teoremas que supostamente impedir a verificação automática de programas. É claro que isto não é verdade; estas questões meramente nos dizer que é possível escrever programas que não pode ser provado ser correta ou incorreta . Isso não nos impede de construir programas que são comprovadamente correta.

O problema da parada apenas mostra que existem programas que não podem ser verificadas. Uma questão muito mais interessante e mais prático é o que classe de programas pode ser formalmente verificada. Talvez todos os programas alguém se importa sobre poderia (em teoria) ser verificada. ~~Na prática, até agora, apenas pequenas programas têm sido provada correta.~~

Se você estiver realmente interessado no assunto, deixe-me primeiro recomendar David Gries' "The Science of Programming", um trabalho introdutório clássico sobre o tema.

Na verdade, é possível provar programas corrigir em certa medida. Você pode escrever pré-condições e pós-condições e, em seguida, provar que dado um estado que atenda aos pré-requisitos, o estado resultante após a execução irá atender as pós-condições.

Onde fica complicado, no entanto, é loops. Para estes, você também precisa encontrar uma invariante de laço e mostrar terminação correta, você precisa encontrar uma função limite superior sobre o número máximo possível de iterações restantes depois que cada loop. Você também tem que ser capaz de mostrar que esta diminui em pelo menos um após cada iteração através do laço.

Depois de ter tudo isso para um programa, a prova é mecânico. Mas, infelizmente, não há nenhuma maneira para derivar automaticamente o invariante e funções ligadas por laços. sufixos intuição humana para casos triviais com pequenos laços, mas, realisticamente, programas complexos rapidamente tornar-se intratável.

Em primeiro lugar, por que você está dizendo "programas não pode ser provado"?

O que você quer dizer com "programas" de qualquer maneira?

Se por programas que você está significado algoritmos você não sabe Kruskal de? de Dijkstra? MST? do prim? Binary Search? Mergesort? DP? Todas essas coisas têm modelos matemáticos que descrevem seus comportamentos.

descrever. que a matemática não explicar o porquê das coisas que simplesmente desenha um retrato do como. Eu não posso provar-lhe que o sol nascerá amanhã no Oriente, mas eu posso mostrar os dados onde ele vem fazendo isso no passado.

Você disse: "Se você escrever um programa de computador, como é que você pode tirar obras comprovadas anteriores e usá-los para mostrar a verdade do seu programa? Você não pode uma vez que nenhum existe"

Wait? Você não pode? http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis

Eu não posso mostrar-lhe "verdade" Eu um programa tanto quanto eu não posso mostrar-lhe a "verdade" sobre a língua. Ambos são representações de nossa compreensão empírica do mundo. Não em "verdade". Colocando tudo jargão lado eu posso demonstrar-lhe matematicamente que um algorith mergesort irá classificar os elementos em uma lista com O (nlogn) performance, que uma Dijkstra vai encontrar o caminho mais curto em um grafo ponderado, ou que o algoritmo de Euclides vai encontrá-lo o maior divisor comum entre dois números. A "verdade no meu programa" nesse último caso, talvez que eu vou encontrar o máximo divisor comum entre dois números, você não acha?

Com uma equação de recorrência posso delinear-lhe como o seu programa de Fibonacci funciona.

Agora, é computador programando uma arte? Eu com certeza acho que é. Tanto quanto a matemática.

Eu não venho de um fundo matemático, então perdoe a minha ignorância, mas o que significa "para provar um programa" significa? O que você está provando? A correção? A correção é uma especificação que o programa deve verificar para ser "correta". Mas esta especificação é decidido por um ser humano, e como você verificar que esta especificação está correta?

Para minha mente, existem erros no programa, porque os seres humanos têm dificuldades expressar o que eles realmente querem. alt texto http://www.processdevelopers.com/images/PM_Build_Swing.gif

Assim que você está provando? Erros causados ??por falta de atenção?

Além disso, quais são os axiomas da programação? As verdades muito atômicas do campo?

Eu TA'ed um curso chamado Programação de Contrato Based (curso homepage: http: // www.daimi.au.dk/KBP2/ ). Aqui o que eu posso extrapolar a partir do curso (e outros cursos que eu tomei)

Você tem que formalmente (matematicamente) definem a semântica do seu idioma. Vamos pensar em uma linguagem de programação simples; um que tem apenas variáveis ??globais, ints, matrizes int, aritmética, if-then-else, while, cessão e não fazer nada [provavelmente você pode usar um subconjunto de qualquer língua dominante como uma "implementação" deste].

Um estado de execução seria uma lista de pares (nome da variável, valor da variável). Leia "{Q1} S1 {Q2}" como "execução declaração S1 leva você a partir Q1 estado de execução para Q2 Estado".

Um axioma seria então "if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}". Ou seja, se declaração S1 leva você a partir Q1 estado para Q2, e declaração S2 leva do Q2 para Q3, então. "S1; S2" (S1 seguido por S2) leva você a partir Q1 estado para Q3 estado

Outro axioma seria "if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}".

Agora, um pouco de requinte:. Do no {} 's Qn seria realmente afirmações sobre estados, não afirma-se

Suponha que M (para fora, A1, A2) é uma declaração que faz uma fusão de duas matrizes ordenadas e armazena o resultado em out, e que todas as palavras que eu uso no próximo exemplo foram expressas formalmente (matematicamente). Então "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}" é a alegação de tha M implementa corretamente o algoritmo merge.

Pode-se tentar provar isso usando os axiomas acima (alguns outros provavelmente seria necessário. É provável que você precisa de um loop, para um).

Espero que isso ilustra um pouco do que programas que provam olhar poder correta como. E confiem em mim: é preciso um muito do trabalho, mesmo para algoritmos aparentemente simples, para provar que estão corretas. Eu sei, eu li um monte de tentativas; -)

[se você ler este: o mão-in foi bom, é todos os outros que causaram-me dores de cabeça; -)]

Claro que pode, como outros já publicados.

Provando uma pequena sub-rotina correta é um bom exercício que IMHO cada graduação em um programa de graduação de programação relacionada deveria ser necessário para fazer. Ele lhe dá uma grande visão sobre o pensamento sobre como fazer o seu código claro, facilmente reviewable e sustentável.

No entanto, no mundo real é de uso prático limitado.

Em primeiro lugar, assim como os programas têm bugs, então, fazer provas matemáticas. Como provar que uma prova matemática é realmente correta e não tem quaisquer erros? Você não pode. E para contra-exemplo, qualquer número de provas matemáticas publicados tiveram erros descobertos neles, às vezes anos mais tarde.

Em segundo lugar, você não pode provar que um programa está correta sem ter 'a priori' uma definição inequívoca de que o programa é suposto fazer. Mas qualquer definição inequívoca do que um programa é suposto fazer é um programa. (Embora possa ser um programa em algum tipo de linguagem de especificação que você não tem um compilador para.) Portanto, antes que você possa provar que um programa está correto, você deve primeiro ter um outro programa que é equivalente e é conhecido com antecedência estar correto. Então QED a coisa toda é fútil.

Eu recomendaria rastrear o clássico " No Silver Bullet " artigo de Brooks.

Há muita pesquisa nesta área .. como já foi dito, as construções dentro de uma linguagem de programação são complexas, e isso só piora, ao tentar validar ou provar por quaisquer entradas de dados.

No entanto, muitas línguas permitir especificações, sobre o que as entradas são aceitáveis ??(pré-condições), e também permitem especificar o resultado final (pós-condições).

Essas línguas incluem:. B, Evento B, Ada, Fortran

E, claro, existem muitas ferramentas que são projetados para nos ajudar a provar certas propriedades sobre os programas. Por exemplo, para provar a liberdade de impasse, pode triturar o seu programa através do SPIN.

Há também muitas ferramentas lá fora, que também nos ajudam a detectar erros de lógica. Isto pode ser feito através de análise estática (goanna, satabs) ou execução real de código (gnu valgrind?).

No entanto, não há uma ferramenta que realmente permite que se provar um programa inteiro, desde o início (especificação), implementação e implantação. O método B chega perto, mas a sua verificação de implementação é muito, muito fraco. (Assume-se que os seres humanos são infalible na tradução de speicficaiton em implmentation).

Como uma nota lateral, quando se utiliza o método B, você encontra-se freqüentemente a construção de provas complexas a partir de axiomas menores. (E o mesmo se aplica para outros provadores de teoremas exhasustive).

Eles podem. Passei muitas horas como um calouro de faculdade fazendo provas programa de correção.

A razão não é prático em uma escala macro é que escrever uma prova de um programa tende a ser muito mais difícil do que escrever o programa. Além disso, os programadores hoje tendem a construir sistemas, e não funções ou programas de escrita.

Em uma escala micro, eu às vezes fazê-lo mentalmente para funções individuais, e tendem a organizar meu código para torná-los fáceis de verificar.

Há um famoso artigo sobre o software do ônibus espacial. Eles fazem provas, ou algo equivalente. É incrivelmente caro e demorado. Esse nível de verificação pode ser necessário para eles, mas para qualquer tipo de consumidor ou empresa de software comercial, com as técnicas atuais, você vai ter o seu almoço comido por um concorrente que oferece uma solução de 99,9% a 1% do custo. Ninguém vai pagar US $ 5000 para um MS Office que é marginalmente mais estável.

Se você está procurando a confiança, a alternativa para programas provando é testá-las. Isto é mais fácil de entender e pode ser automatizado. Ele também permite que para a classe de programas para os quais as provas não são matematicamente possível, como descrito acima.

Acima de tudo, nenhuma prova é um substituto para passar testes de aceitação: *

Só porque um programa realmente faz o que diz que faz, não significa que ele faz o que o usuário quer que ele faça.

A menos você pode provar que o que diz que faz é o que o usuário diz que eles querem.

O que você então tem que provar é que eles realmente quer , porque, sendo um usuário, eles quase certamente não sabem o que querem. etc. reductio ad absurdum.

* não à unidade de menção, a cobertura, funcional, integração e todos os outros tipos de testes.

Espero que isso ajude você em seu caminho.

Algo que não tenha sido mencionado aqui é a B - Método que é um método formal sistema baseado. Ele foi usado para desenvolver o sistema de segurança do Paris subterrânea. Existem ferramentas disponíveis para apoio B e desenvolvimento Evento B, nomeadamente Rodin .

Não apenas você pode provar programas, você pode deixar seus programas construto de computador de provas. Veja Coq . Então você nem precisa se preocupar com a possibilidade de ter cometido um erro na sua implementação.

de Godel Teoremas não obstante ... O que seria o ponto ? O "verdades" simplista que gostaria de provar? O que você quer retirar dessas verdades? Enquanto eu coma estas palavras ... onde está a praticidade?

Os programas podem ser comprovado. tranquila É fácil se você escrevê-los em linguagem como por exemplo ML padrão de New Jersey (SML / NJ).

Sua declaração é grande por isso é pegar muitos peixes.

A linha inferior é: alguns programas podem ser definitivamente provada correta. Todos os programas podem não ser provada correta.

Aqui está um exemplo trivial que, lembre-se, é exatamente o mesmo tipo de prova que destruiu set teoria de volta no dia: fazer um programa que pode determinar se si é correta, e se verificar que ele é correta, dar uma resposta incorreta.

Este é o teorema de Gödel, pura e simples.

Mas isso não é tão problemático, uma vez que pode revelar muitos programas.

Vamos assumir uma linguagem puramente funcional (ou seja, Haskell). Os efeitos secundários podem ser tomadas muito limpa em conta em tais idiomas.

Provando que um programa produz o resultado correto requer que você especifique:

a correspondência entre os tipos de dados e conjuntos matemáticos

a correspondência entre as funções Haskell e funções matemáticas

um conjunto de axiomas especificando quais as funções que estão autorizados a construção de outros, ea construção correspondente no lado matemático.

Este conjunto de especificações é chamado denotacional semântica . Eles permitem que você provar a razão sobre os programas que usam a matemática.

A boa notícia é que a "estrutura de programas" (ponto 3 acima) e a "estrutura de conjuntos matemáticos" são bastante semelhantes (a palavra de ordem é topos ou cartesiano categoria fechada ), então 1 / as provas que você faz no lado de matemática vai ser facilmente transferido para construções programáticas 2 / os programas que você escreve são facilmente demonstrado ser matematicamente correto.

Leia a parada problema (que é sobre a dificuldade de provar algo tão simples como se um programa completa ou não). Fundamentalmente, o problema está relacionado ao teorema da incompletude de Gödel.

Algumas partes de programas pode ser provado. Por exemplo, o compilador C # que estaticamente verificar e tipo garantia de segurança, se a compilação for bem-sucedido. Mas eu suspeito que o núcleo da sua pergunta é provar que um programa executa corretamente. Muitos (não ouso dizer a maioria) algoritmos podem ser provou ser correta, mas todo um programa provavelmente não pode ser provado estaticamente devido ao seguinte:

A verificação exige todos os ramos possíveis (chamadas, ifs e Interupts) a serem percorridos, o que no código do programa avançado tem complexidade de tempo super-cúbico (portanto, nunca será concluída num prazo razoável).

Algumas técnicas de programação, quer através de realização de componentes ou usando a reflexão, faz com que seja impossível prever estaticamente execução de código (ou seja, você não sabe como outro programador irá usar a sua biblioteca, e o compilador tem um tempo difícil prever como reflexo no um consumidor irá chamar funcionalidade.

E essas são apenas algumas ...

Se o programa tem um premissas objetivas e iniciais bem definidas (ignorando Godel ...) pode ser comprovada. Encontrar todos os números primos, x, por 6 <= x <= 10, a sua resposta é 7 eo que pode ser comprovada. Eu escrevi um programa que desempenha NIM (o primeiro programa Python Eu já escrevi) e, em teoria, o computador sempre vence após o jogo cai em um estado em que o computador pode ganhar. Eu não tenho sido capaz de provar isso como verdade, mas é verdade (matematicamente por uma prova soma binário digital) Eu acredito que a menos que eu tenha cometido um erro no código. Eu fiz um erro, não a sério, alguém pode me dizer se este programa é superável?

Há alguns teoremas matemáticos que foram "provados" com código de computador como o quatro cores teorema . Mas há objeções, porque, como você disse, você pode provar o programa?

Além disso, quais são os axiomas da programação? As verdades muito atômicas do campo?

são os opcodes as "verdades atômicas"? Por exemplo, ao ver ...

mov ax,1

... talvez não um assert programador como axiomático que, salvo um problema de hardware, depois de executar esta declaração registo ax da CPU que agora contêm 1?

Se você escrever um programa de computador, como é que você pode tirar obras comprovadas anteriores e usá-los para mostrar a verdade do seu programa?

O "trabalho prévio", em seguida, pode ser o ambiente de tempo de execução em que o programa de novas execuções.

O novo programa pode ser provado:. Além de provas formais, pode ser provado "por inspeção" e por várias formas de "teste" (incluindo "teste de aceitação")

Como você prova um Picasso?

Se o software é mais como design industrial ou engenharia de como a arte, a melhor pergunta seria "como você provar uma ponte, ou um avião?"

provando um programa correto só pode ser feito em relação à especificação do programa; É possível, mas caro / demorado

alguns sistemas CASE produzir programas mais passíveis de provas do que outros - mas novamente, isso depende de uma semântica formal da especificação ...

... e assim como você provar a especificação correta? Certo! Com mais especificações!

Eu li um pouco sobre isso, mas há dois problemas.

Em primeiro lugar, você não pode provar alguma coisa abstrata chamada correção. Você pode, se as coisas estão configurados corretamente, provar que dois sistemas formais são equivalentes. Você pode provar que um programa implementa um conjunto de especificações, e é mais fácil de fazer isso através da construção a prova e programa mais ou menos em paralelo. Portanto, as especificações devem ser suficientemente pormenorizadas para fornecer algo a provar contra, e , portanto, a especificação é efetivamente um programa . O problema de escrever um programa para satisfazer um propósito torna-se o problema de escrever uma especificação formal detalhada de um programa para satisfazer um propósito, e isso não é necessariamente um passo em frente.

Em segundo lugar, os programas são complicados. Portanto, são provas de correção. Se você pode cometer um erro escrevendo um programa, com certeza você pode fazer uma prova. Dijkstra e Gries me disse, essencialmente, que se eu fosse um matemático perfeito que eu poderia ser um bom programador. O valor aqui é que provando e programação são dois processos de pensamento um tanto diferentes, e pelo menos na minha experiência eu fazer diferentes tipos de erros.

Na minha experiência, provando programas não é inútil. Quando eu estou tentando fazer algo que eu posso descrever formalmente, comprovando a implantação elimina corrigir uma série de erros difíceis de encontrar, deixando principalmente os mudos, que eu posso pegar facilmente em testar. Em um projeto que deve produzir código extremamente livre de bugs, ele pode ser um complemento útil. Não é adequado para cada aplicação, e é, sem dúvida nenhuma bala de prata.

Como outros apontaram, (alguns) programas podem realmente ser comprovada.

Um problema na prática, porém, é que você precisa primeiro algo (ou seja, uma suposição ou teorema) que pretende provar. Então, para provar alguma coisa sobre um programa que você primeiro precisa de uma descrição formal de que ele deve fazer (por exemplo, pré e pós-condições).

Em outras palavras, você precisa de uma especificação formal do programa. Mas conseguir até mesmo uma (muito menos de uma rigorosa formal) especificação razoável já é uma das coisas mais difíceis no desenvolvimento de software. Por isso, é geralmente muito difícil de provar interessante coisas sobre um programa (do mundo real).

No entanto, existem algumas coisas que podem ser (e foram) mais facilmente formalizados (e comprovadas). Se você pode, pelo menos, provar que seu programa não irá falhar, que já é alguma coisa: -).

BTW, alguns avisos do compilador / erros são, essencialmente, (simples) provas sobre um programa. Por exemplo, o compilador Java irá provar que você nunca acessar uma variável não inicializada em seu código (caso contrário, ele vai te dar um erro do compilador).

Eu não li todas as respostas, mas a forma como eu vejo, provando programas é inútil, é por isso que ninguém faz isso.

Se você tem um projeto / médio relativamente pequeno (digamos, 10k linhas de código), então, a prova é, provavelmente, vai ser também 10k linhas, se não mais.

Pense nisso, se o programa pode ter erros, a prova também pode ter "bugs". Talvez você vai precisar de uma prova para a prova!

Outra coisa a considerar, os programas são muito, muito formal e preciso. Você não pode ficar mais rigoroso e formal, porque o código do programa deve ser executado por uma máquina muito burra.

Enquanto provas vão ser lido por seres humanos, para que eles tendem a ser menos rigoroso do que o código real.

As únicas coisas que você vai querer provar que são algoritmos de baixo nível que operam em estruturas de dados específicos (por exemplo, quicksort, inserção para uma árvore binária, etc).

Essas coisas são um pouco complicado, não é imediatamente óbvio por que eles trabalham e / ou se eles sempre funcionará. Eles também são blocos de construção básicos para todos os outros softwares.

A maioria das respostas incidiu sobre a prática e isso é ok: na prática, você não se preocupam com prova formal. Mas o que é, em teoria?

Os programas podem ser comprovados, assim como uma lata enunciado matemático. Mas não no sentido que você quis dizer! Em qualquer estrutura poderosa suficiente, há afirmações matemáticas (e programas) que não podem ser comprovadas! Consulte aqui

Tanto barulho aqui, mas eu vou gritar com o vento de qualquer maneira ...

"Prove correto" tem significados diferentes em contextos diferentes. Em sistemas formais , "provar corretas" significa que a fórmula pode ser derivada de outras comprovada (ou axiomática ) fórmulas. "Prove correta" na programação simplesmente código mostra como equivalente a uma especificação formal. Mas como você provar formal especificação correta? Infelizmente, não há nenhuma maneira de mostrar uma especificação para ser livre de bugs ou uma solução de qualquer problema do mundo real que não seja através de testes.

Apenas meus 2 centavos, somando-se o material interessante já está lá.

De todos os programas que não podem ser comprovadas, as mais comuns são aqueles que realizam IO (alguma interação unpredictible com o mundo ou dos usuários). provas Mesmo automatizados, por vezes, esquecer que os programas de "run "provado" em algum hardware físico, não o ideal descrito pelo modelo.

Por outro lado provas matemáticas não se importam grande parte do mundo. Uma questão recorrente com a matemática é se ele descreve qualquer coisa real. Ele é levantada cada vez que algo novo como números imaginários ou espaço não-euclidiana é inventado. Então a pergunta é esquecido como estas novas teorias são tão boas ferramentas. Como um programa de bom, ele simplesmente funciona.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow