Esta é uma pergunta de acompanhamento para
Qual é a diferença entre provas e programas (ou entre proposições e tipos)?
O programa que corresponderia a uma prova não-construtiva (clássica) do formulário ? (Assume-se que alguma relação decidíveis interessante por exemplo, não -ésimo TM não parar em passos).
(ps: estou postando esta pergunta em parte porque estou interessado em aprender mais sobre o que Neel quer dizer com " a tradução de Godel-Gentzen é uma transformação de passagem contínua" em seu comentário .)
Respostas:
Esta é uma pergunta interessante. Obviamente, não se pode esperar para ter um programa que decide para cada se ∀ k T ( e , k ) possui ou não, pois isso iria decidir a suspensão problema. Como já mencionado, existem várias maneiras de interpretar provas computacionalmente: extensões de Curry-Howard, capacidade de realização, dialética e assim por diante. Mas todos interpretariam computacionalmente o teorema que você mencionou mais ou menos da seguinte maneira.e ∀ K t( e , k )
Para simplificar, considere o teorema clássico equivalente
(1)∃ i ∀ j ( ¬ T( e , j ) → ¬ T(e,i))
Este é (construtivamente), equivalente ao mencionado porque dada podemos decidir se ∀ k T ( e , k ) possui ou não, basta verificar o valor do ¬ T ( e , i ) . Se ¬ T ( e , i ) mantém então ∃ i ¬ T ( e , i ) e, portanto, ¬ ∀ i T ( e , i ) . Se por outro ladoi ∀kT(e,k) ¬T(e,i) ¬T( E , i ) ∃ i ¬ T( E , i ) ¬ ∀ i T( E , i ) não se sustenta então por (1) temos ∀ j ( ¬ T ( e , j ) → ⊥ ) que implica ∀ j T ( e , j ) .¬ T( E , i ) ∀ j ( ¬ T( e , j ) → ⊥ ) ∀ j t( e , j )
Agora, novamente, não podemos computar em (1) para cada e dado, porque resolveríamos novamente o Problema da Parada. O que todas as interpretações mencionadas acima fariam é olhar para o teorema equivalenteEu e
(2)∀f∃i′(¬T(e,f(i′))→¬T(e,i′))
A função é chamada de função Herbrand. Ele tenta calcular um contra-exemplo j para cada testemunha em potencial i . É claro que (1) e (2) são equivalentes. Da esquerda para a direita, isso é construtivo, basta considerar i ′ = i em (2), onde i é a testemunha assumida de (1). Da direita para a esquerda, é preciso raciocinar classicamente. Suponha que (1) não fosse verdade. Então,f j i i′=i i
(3)∀i∃j¬(¬T(e,j)→¬T(e,i))
Seja uma função testemunhando isso, ief′
(4)∀i¬(¬T(e,f′(i))→¬T(e,i))
Agora, pegue em (2) e temos ( ¬ T ( e , f ′ ( i ' ) ) → ¬ T ( e , i ' ) ) , para alguns i ' . Mas, tomando i = i ' em (4), obtemos a negação disso, contradição. Portanto (2) implica (1).f=f′ (¬T(e,f′(i′))→¬T(e,i′)) i′ i=i′
Portanto, temos que (1) e (2) são classicamente equivalentes. Mas o interessante é que (2) agora tem uma testemunha construtiva muito simples. Simplesmente tome se T ( e , f ( 0 ) ) não se mantiver, porque a conclusão de (2) é verdadeira; ou então tome i ′ = 0 se T ( e , f ( 0 ) ) se mantém, porque então ¬ T ( e , f ( 0 )i′=f(0) T(e,f(0)) i′=0 T(e,f(0)) não se mantém e a premissa de (2) é falsa, tornando-a novamente verdadeira.¬T(e,f(0))
Portanto, a maneira de interpretar computacionalmente um teorema clássico como (1) é olhar para uma formulação (classicamente) equivalente que pode ser comprovada construtivamente, no nosso caso (2).
As diferentes interpretações mencionadas acima divergem apenas na maneira como a função exibida. No caso da realização e da interpretação dialética, isso é explicitamente dado pela interpretação, quando combinada com alguma forma de tradução negativa (como a de Goedel-Gentzen). No caso de extensões Curry-Howard com operadores call-cc e continuation, a função f decorre do fato de o programa poder "saber" como um determinado valor (no nosso caso i ) será usado, então f é a continuação do programa em torno do ponto em que i é computado.f f i f i
Outro ponto importante é que você deseja que a passagem de (1) para (2) seja "modular", ou seja, se (1) for usado para provar (1 '), sua interpretação (2) deverá ser usada de maneira semelhante para provar a interpretação de (1 '), digamos (2'). Todas as interpretações mencionadas acima fazer isso, incluindo a tradução Gödel-Gentzen negativo.
fonte
É bem sabido que a aritmética clássica e intuicionista são equiconsistentes.
Uma maneira de mostrar isso é através dos "embates negativos" da lógica clássica na lógica intuicionista. Então, suponha que são fórmulas da aritmética clássica de primeira ordem. Agora, podemos definir uma fórmula da lógica intuicionista da seguinte maneira:ϕ
Então, como você deve pensar sobre isso intuitivamente?
Agora, graças a Curry-Howard, sabemos como interpretar provas na lógica intuicionista como programas funcionais. Portanto, uma resposta possível (mas não a única) à pergunta "qual é o conteúdo construtivo de uma prova clássica?" é o seguinte:
Ou seja, se você obtém não-A e não-A, pode passar a primeira negação para a segunda para derivar a contradição que deseja.
Agora, o que são transformações no estilo de passagem de continuação?
Agora,
Eu vi "uma" transformação do CPS, pois, como mencionei anteriormente, existem muitas traduções negativas que permitem provar esse teorema, e cada uma corresponde a uma transformação diferente do CPS. Em termos operacionais, cada transformação corresponde a uma ordem de avaliação diferente . Portanto, não há uma interpretação computacional única da lógica clássica, pois você tem opções a fazer e as diferenças têm características operacionais muito diferentes.
fonte
Existem conferências inteiras sobre o tema de provas não construtivas como programas , e eu não sou especialista no assunto. Acima, Neel Krishnaswami aludiu a uma resposta mais longa que ele está preparando, o que, a julgar pelo seu trabalho aqui, será excelente. Esta é apenas uma amostra de uma resposta.
fornece o código O'Caml:
A introdução mais clara a isso que eu vi está na "noção de controle de fórmulas como tipos de Tim " .
fonte
callcc
para o Schemecallcc
. Então você pode realmente experimentar as coisas.