8. Uncomputable Functions

Hello everyone, welcome to this lecture so just a quick recap; in the last lecture we discussed about Cantor’s diagonalization argument. And we saw examples of uncountable sets; the plan for this lecture is as follows. We will discuss about computable and uncomputable functions and we will discuss about the existence of uncomputable functions.

This introduction sets the stage for the lecture by briefly reviewing what was covered previously. It highlights the transition from Cantor's diagonalization argument and uncountable sets to the main focus of the current lecture: computable versus uncomputable functions. The lecturer prepares the audience for an exploration into the nature of functions that can and cannot be computed.

Consider a library filled with books where each book represents a different function. Just like some books are written in languages that can only be understood by certain people (computable functions), there are others that are written in languages no one can understand, regardless of their literacy (uncomputable functions).

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.

A computable function is defined as one for which a computer program can be created to compute its value for every input in its domain. The emphasis is on the existence of such a program rather than its efficiency or resource usage. If no program can be constructed for a certain function, that function is classified as uncomputable.

Think of a vending machine that offers a variety of snacks. If you can press a button for any snack and the vending machine will always dispense it (computable function), it's reliable. However, if there is no button for your desired snack and the machine cannot produce it, then it's akin to an uncomputable function—it simply cannot fulfill that request.

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.

The speaker intends to prove the existence of uncomputable functions, stating that no matter how much time or resources are allocated, certain functions cannot be computed by any program. This leads into a deeper exploration of the limitations of computational power.

Imagine a magical task that requires solving a riddle that no person has ever cracked. No matter how intelligent or resourceful they are, they simply cannot find the answer. This reflects uncomputability—it highlights the limits of what can actually be achieved, even with the best resources at hand.

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.

The lecturer points out that, based on previous discussions, the collection of valid programs that can be written in programming languages is countable, meaning we can enumerate or list them, even though there are infinitely many. This sets the stage for the argument that there are functions beyond the scope of these programs.

Think of counting the number of books in a library where every book has a unique title—this is akin to enumerating programs. However, just because we can list the books does not mean that they cover every story or topic that exists.

We will prove that the cardinality of this collection of all possible functions is not א0 that is what we are going to prove. That means what we are going to show is that we have more functions than the number of possible programs.

The objective here is to demonstrate that there are more functions mapping positive integers to integers than there are valid programs. The speaker will establish that the set of all possible functions is uncountable, significantly exceeding the countable set of valid programs.

If you imagine a scenario with a set of recipes, where each recipe corresponds to a function, and the number of ingredients represents the programs, there are infinitely more ways to mix and match ingredients than there are recipes themselves. This analogy illustrates the idea of having more potential functions than can be represented by a finite number of recipes.

This is the set of all real numbers between [0,1) including 0 that is why you have the square bracket within 0 but excluding one. So this set is already known to be uncountable what we will show is, we will show an injective mapping from this set to the collection calligraphic F.

The proof aims to demonstrate an injective mapping from the uncountable set of real numbers in the range [0,1) to the collection of functions, thereby establishing that the collection of possible functions is also uncountable. Since the set of real numbers is known to be uncountable, this proves the same for the function set.

Think of assigning a unique address to every house on a street. An injective mapping ensures that no two houses share the same address—just like how two different real numbers translate to two different functions. This process illustrates the concept of injective mappings in a concrete manner.

So that is why clearly this function is an injective function. So we have shown here that indeed the set of all possible functions from the set of positive integers to the set {0,…,9} is an uncountable set.

With the completion of the proof, it is confirmed that the set of all possible functions from positive integers to the digit set is uncountable. This finding concludes that there are indeed more functions than valid programs, hence proving the existence of uncomputable functions.

Consider a vast network of routes in a city; there are numerous possible paths (functions) from point A to B that are not depicted on the city map (valid programs). Just as these paths exist but remain untraced, uncomputable functions exist beyond the reach of any programming language.

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.

The existence of uncomputable functions signifies the limitations of computation and algorithms. It suggests that there are computational tasks that cannot be solved no matter the resources at hand, reshaping our understanding of computer science capabilities.

Imagine if there were tasks where a manual cannot guide you, like figuring out a relationship puzzle with no startling insights despite all the clues. This reflects the nature of uncomputable functions—there are inherent limits to what can be solved algorithmically.

--