Clase de funciones computables por Coq

Dado que no permite el cómputo no determinante, Coq no es necesariamente completo de Turing. ¿Cuál es la clase de funciones que Coq puede calcular? (¿hay una caracterización interesante de los mismos?)

computability pl.programming-languages coq Steve
fuente

Respuestas:

Benjamin Werner ha demostrado la capacidad de interpretación mutua de ZFC con innumerables inaccesibles y el cálculo de construcciones inductivas, en su papel Conjuntos en tipos, tipos en conjuntos .

Esto significa, más o menos, que cualquier función que se pueda demostrar que es total en ZFC con innumerables inaccesibles se puede definir en Coq. Entonces, a menos que sea un teórico de conjunto que trabaje en cardenales grandes, es poco probable que cualquier función computable que alguna vez haya deseado no pueda definirse en Coq.

Neel Krishnaswami
fuente

Excepto un intérprete de Coq ...

Jules

En realidad, puede implementar un intérprete de Coq (de hecho, funciones recursivas generales arbitrarias) dentro de Coq. Si CIC es consistente, no podrá probar que el intérprete es una función total, por supuesto, pero definitivamente puede implementarlo.

Neel Krishnaswami

A_{⊥} ≜ ν α . A + α

$A_\bot \triangleq \nu \alpha.\; A + \alpha$

c o n t e x t \to t e r m \to t y p e \to {b o o l}_{⊥}

$\mathsf{context} \to \mathsf{term} \to \mathsf{type} \to \mathsf{bool}_\bot$

@Neel: Eso es trampa. Y por una buena razón, de lo contrario tendríamos una inconsistencia.

Andrej Bauer

Es una trampa porque se supone que la función de evaluación evalúa cosas, no le da una falta de respuesta.

Andrej Bauer