Por que o Verificador de provas é necessário no Código de transporte de provas

9

No artigo clássico PLDI'98 de Necula, "O design e implementação de um compilador de certificação", o verificador de alto nível usa:

  1. VCGen para gerar condições de verificação (predicados de segurança)
  2. Provador do teorema da lógica de primeira ordem para provar as condições
  3. Verificador de prova LF para verificar a prova da etapa (2)

Estou um pouco confuso com o passo (3). Por que é necessário? Apenas (1) e (2) não serão suficientes? Por que não confiamos apenas na prova gerada por um provador de teoremas?

proof-theory automated-theorem-proving program-verification RAM
fonte

Respostas:

19

O objetivo do verificador de provas é minimizar a base de computação confiável .

Por ter um verificador de provas, nem o compilador nem o provador de teoremas precisam estar corretos. O artigo faz este ponto na página 3:

Neither the compiler nor the prover need to be correct in order to be guaranteed to   
detect incorrect compiler output. This is a significant advantage since the VCGen and  
the  proof checker are significantly simpler than the compiler and the prover.

Um verificador de provas é apenas um par de linhas de código e pode ser inspecionado manualmente quanto à correção. Por outro lado, um provador automatizado com bom desempenho é extremamente complexo e improvável de ser correto, embora com provadores bem testados e amplamente utilizados, os erros ocorram em casos extremos que podem não ser fáceis de desencadear. Veja o código LOC C de 30k que compõe o Lingeling , um solucionador de SAT de última geração para ver o quão complicado pode ser o teste de teoremas automatizados. Sem um verificador de provas, você teria que provar que estava correto. Isso está além do que podemos fazer economicamente em 2015.

Martin Berger
fonte
Estou surpreso que as provas construídas pelos ATPs possam ser de buggy. (Eu pensei que o ATP pode ser incompleto, mas não doentio / com erros) Estou menos informado aqui. Ficarei feliz em saber se existem casos conhecidos de erros caros nas provas geradas pelos ATPs.
Ram
3
@Ram Existem milhares de pequenos erros de sonoridade na história de qualquer provador automático de teoremas. Veja, por exemplo, stackoverflow.com/questions/12281085/… ou o histórico de revisões de qualquer ferramenta desse tipo no github.
Cody
@Ram Além dos bons conselhos de Cody, recomendo aprender com a experiência: escreva um pouco de ATP, como um solucionador básico de SAT. Isso pode ser feito em algumas linhas de código. Em seguida, tente fazer com que ele funcione bem adicionando, por exemplo, aprendizado de cláusulas, literais assistidos ou heurísticas interessantes de seleção de variáveis. Então, pense sobre a experiência ...
Martin Berger