O'Reilly logo

Computation, Proof, Machine by Marion Roman, Pierre Guillot, Gilles Dowek

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter Eight Constructive Proofs and Algorithms

WHAT DOES THE NOTION of constructive proof have to do with the subject of this book, namely computation? The notions of computation and algorithm did not originally play such an important part in the theory of constructivity as in, say, the theory of computability. However, behind the notion of constructive proof lay the notion of algorithm.

Cut Elimination

We have seen that proofs of existence resting on the principle of excluded middle do not always contain a witness. On the other hand, a proof of existence that does not use the excluded middle always seems to contain one, either explicitly or implicitly. Is it always so, and can this be demonstrated?

Naturally, the possibility of finding a ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required