Testando se uma prova arbitrária é circular?

13

Eu estava pensando em provas e tive uma observação interessante. Portanto, as provas são equivalentes aos programas pelo isomorfismo de Curry-Howard, e as provas circulares correspondem a uma recursão infinita. Mas sabemos do problema da parada que, em geral, testar se um programa arbitrário se repete para sempre é indecidível. Por Curry-Howard, isso significa que não existe um "verificador de provas" que possa determinar se uma prova usa raciocínio circular?

Sempre achei que as provas deveriam ser compostas de etapas facilmente verificáveis ​​(que correspondem a aplicações de regras de inferência), e verificar todas as etapas dá a você a confiança de que a conclusão se segue. Mas agora estou me perguntando: talvez seja realmente impossível escrever um verificador de provas, porque não há como contornar o problema da parada e detectar o raciocínio circular?

logic curry-howard hewasonlyacat
fonte

Respostas:

15

A grande maioria dos sistemas de prova não permite provas circulares infinitas, mas o faz tornando seus idiomas não-Turing completos.

Y∀uma.(uma→uma)→uma

umaumauma

A chave aqui é que o combinador Y é incorporado a um idioma, é tomado como um axioma. Portanto, se você quer que isso não lhe cause problemas, basta se livrar dele como um axioma!

A maioria dos sistemas formais de prova, por isso, exige que sua recursão seja bem fundamentada. Eles só aceitam funções que eles podem provar que serão interrompidas. E, como resultado, eles rejeitam alguns programas que são interrompidos, mas para os quais não podem provar.

Coq faz isso de uma maneira bastante limitada: requer apenas que qualquer função recursiva tenha um argumento em que qualquer chamada recursiva use apenas versões estritamente menores desse argumento. O Agda faz algo semelhante, mas com uma verificação um pouco mais sofisticada para aceitar mais alguns programas.

jmite
fonte
1
Coq descarta alguns teoremas legítimos que você poderia provar? Ou sempre existem soluções alternativas para quando o verificador de totalidade é muito conservador? (Presumo que a resposta seja a mesma para outros assistentes de prova com base na teoria do tipo dependente?)
stovetop
1
@boyers FWIW, no Coq, pode-se usar Functionou Program Fixpointconstruções para provar que alguma função é total se o verificador de totalidade falhar. Um exemplo simples é a função de classificação por mesclagem nas listas. É preciso provar manualmente que dividimos listas (de tamanho> 1) em sublistas estritamente menores.
Anton Trunov
@boyers Sim, tem que haver coisas que você não pode provar em Coq, pelo primeiro teorema de Gödel. Na prática, é raro encontrá-los, mas sempre há o argumento diagonal: o Coq não pode provar o próprio Coq, só pode provar um subconjunto (um subconjunto muito grande, mente, incluindo todos os recursos, mas com um limite mais baixo de quanta recursão ele aguenta). Lembro-me de ler que a teoria de Coq é equivalente aos axiomas de Peano mais a existência de um certo ordinal grande (e, portanto, as provas que supõem um ordinal ainda maior não se encaixam), mas não consigo encontrar a referência agora.
Gilles 'SO- stop be evil'
@AntonTrunov Neste contexto, Programe similares, são um arenque vermelho. Eles não mudam a teoria. O que eles fazem é açúcar sintático para usar uma medida em uma prova: em vez de pensar que o objeto em que você está interessado fica menor, você adiciona um nível de indireção: calcule que outro objeto fique menor (por exemplo, tamanho) e prove que ele fica menor. Veja a Wfbiblioteca.
Gilles 'SO- stop be evil'
@Gilles Eu assumi que o contexto era sobre o lado prático (concreto), como quando a heurística da Coq falha ... Você poderia tentar encontrar o artigo que mencionou? Um link seria muito apreciado.
Anton Trunov 31/05