Introduction to Uncomputability

Abstract:

The halting problem asks us to decide whether the Turing Machine with Godel number x will halt on a particular input y or not. It is equally 
difficult is to decide whether the Turing Machine x will halt when it is given its own Godel number x as its input.  In fact, the set K of 
machines which halt on themselves is recursively enumerable but not recursive. This means that the complement K is not even recursively 
enumerable. What is the special ingredient in the structure of K which raises the spectre of incomputability? In this talk we shall see that this 
is caused by a property called creativeness.  And does incomputability arise in only one way? Is there an incomputable set which is not 
creative? We shall also see that this is the case by showing how to construct such a set, referred to as a simple set, through a powerful proof 
technique called the priority method.  Despite the technicality of the subject, an effort will be made to give intuitive explanations and insight
 into the topics discussed.