Computability And Incompleteness

author: Errol Martin, EP Martin Consulting
published: April 1, 2009,   recorded: January 2009,   views: 19933


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 1:04:59
Watch Part 2
Part 2 48:03
Watch Part 3
Part 3 56:16
Watch Part 4
Part 4 53:30


In these lectures we cover the following topics: Computability and Recursive Functions, Proof that exactly the partial recursive functions are computable, Gödel’s Incompleteness Theorems, Löb's Theorem.These very deep and very powerful results in metalogic from the 1930s were unexpected. They arose in a context in which it was expected that a finitary proof of consistency of arithmetic would shortly be forthcoming. This followed the proposal by the mathematician David Hilbert (1862-1943) for the complete axiomatisation and formalisation of all mathematical knowledge and proofs. Although committed to formal methods, many of Hilbert’s proofs were existential in nature, which ran counter to the finitistic, constructivist methods of mathematics. To deal with this criticism, Hilbert proposed that the formal methods program should establish that all of the “Ideal” existential arguments could in principle be replaced by “Real” constructive arguments, by showing some sort of conservation result. However, the incompleteness results showed that this ‘program’ could not be carried out in a simple way.

See Also:

Download slides icon Download slides: ssll09_martin_cai.pdf (226.7 KB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Fawzy Hegab, December 17, 2015 at 3:43 p.m.:

Great lecture. thanx for posting it!

Write your own review or comment:

make sure you have javascript enabled or clear this field: