O'Reilly logo

Handbook of Practical Logic and Automated Reasoning by John Harrison

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

7

Limitations

 

 

Most of this book is about positive results: certain logical problems can in principle be automated. Here we consider the limits of automation, showing that algorithms in the usual sense cannot exist for certain logical problems. In particular we show that pure first-order logic is not decidable, and that the theory of natural numbers with addition and multiplication is, in a precise sense, nowhere near decidable. In making our way to these results, we prove Gödel’s famous first incompleteness theorem.

7.1 Hilbert’s programme

The idea of mechanizing reasoning fascinated people long before computers. Specific questions about the scope and limits of mechanization were investigated systematically in the early part of the twentieth ...

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