So what exactly are uncomputable functions; so they are some special type of functions. So say I have function f defined from a set X to a set Y then I will call the function f to be computable if there exists some computer program in a programming language which can compute or give you the value of this function for every possible input from the domain of that function. So mind it I am not focusing here on the running time of the computer program or the resources utilized for the program to give you the value or the output of that function.
I am interested whether there exists a program or not which can give you can give you the output of that function for every input from the domain. If you can write a program in the programming language for such a function I will call that function to be a computable function. Otherwise I will call it uncomputable function. So as per the above definition a function which is not computable will be called an uncomputable function.

So what we now want to prove is that there indeed exists uncomputable function that means it does not matter how much resources time and memory space you provide. And write down a program there always exist some function such that you cannot write down a program respective of resources allowed to compute the output of that function for every possible input. And what will be proof strategy that we will follow to prove this theorem?
So we will begin with some known fact; so just recall that in one of our earlier lectures we proved that the set of all valid programs in any programming language is countable. That means we can enumerate them even though they are infinitely many valid programs. When I say programs I mean to say the valid programs; which complies and give you an output. That means it has a begin instruction and an end instruction and a sequence of arbitrary number of instructions in between the begin and end instructions and it complies and it gives you an output.

Now any program from your collection of valid programs can compute a single function from this collection F. We cannot have the same program which gives you the value of both, function f as well as function f . Because function f and function f will have different characteristics how can it be possible that you have a common program P which simultaneously gives you the output of function f as well as it gives you the function output for f.
You cannot have such special programs; that means if we prove this claim then based on the known fact we come to the conclusion that you have some function in this collection of all possible functions for which you cannot find a matching program in the list of all valid programs in your programming language.

So what is the proof strategy we are using here we are actually arguing about; we are giving here a non-constructive proof. Just to recall what is a non-constructive proof? Non-constructive proofs are used for proving existentially quantified statements. So this statement is an existentially quantified statement because it says that there exists at least one uncomputable function.
And we are logically arguing that indeed one such function exist we are not giving a concerte function for which you can never write a function. We are logically arguing the existence of such a function so that is why this is a non-constructive proof here.

That means if I go back to the previous slide in the proof strategy I have proved my claim that means you have more number of functions than the number of programs which you can write in a programing language. And since each program can give you the output of only a single function from the set of all possible functions you have more functions that the number of programs.
And hence here are some functions for which you do not have a corresponding matching program and that is why you do have uncomputable functions that exist. So that is a very interesting theorem because generally we believe that using computers we can compute anything.