New answers tagged

5 votes

What is the computational power of the Calculus of Constructions?

My understanding of András' answer is that, while it gets the gist correct, his final conclusion is not quite right: The "standard" way to determine the strength of the function space in a ...
user avatar
  • 13.2k
5 votes
Accepted

What is the computational power of the Calculus of Constructions?

There is no total language where all total computable $\mathbb{N} \to \mathbb{N}$ functions are definable. In a total language, an interpreter for the same language is not definable because if it were ...
user avatar

Top 50 recent answers are included