8.3. Cardinality of Sets of Functions and Programs

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.

In this chunk, we learn about the distinction between computable and uncomputable functions. A function is defined as computable if there exists a program that can determine its value for any input. Essentially, computable functions can be executed by a computer program. Conversely, an uncomputable function is one for which no such program can be written, regardless of the resources available. The key takeaway is that not all mathematical functions can be computed by a computer, highlighting limitations in computation.

Think about solving math problems on a calculator. If you can input the formula and get an answer, that's like a computable function. However, imagine a problem where you want to find out whether a specific number can make someone happy—this might be an uncomputable function. No matter how advanced the calculator is, it just can't solve this type of problem.

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.

In this chunk, we are trying to establish that uncomputable functions definitely exist. This means that even if we had unlimited resources—time, memory, etc.—there would still be functions that a program cannot compute. The proof involves demonstrating that there is a larger infinity of functions than there are programs to compute them, thereby supporting the conclusion that some functions are inherently uncomputable.

Imagine trying to organize all the possible books in a library where every single book ever written is included. No matter how much space you create, you can always think of a new book with a different plot. This illustrates how the number of functions can outpace the number of programs, similar to how the number of possible books can be more than any library could ever store.

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.

This chunk sets up a key comparison between the number of programs and the number of possible functions. The claim is that while all programs can be counted (are enumerable), the set of functions, particularly from positive integers to a set of values, is much larger. This difference in cardinality is crucial in proving that uncomputable functions exist, as it shows a disparity between what can be programmed and what functions can theoretically be defined.

Consider a library that can store a certain number of books (programs), but the stories that can be told (functions) are limited only by imagination. Just as you can envision countless stories that no library could hold, there are functions that no program can compute.

We already know a set which is not countable... What is the set? 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.

Here, the lecture introduces the concept of injective mapping, which is used to demonstrate the uncountability of the set of functions. This strategy shows that there exists a clear method to distinguish between two sets based on their cardinalities. By mapping real numbers to functions, and illustrating that different numbers lead to different functions, we strengthen the case that there are more functions than there are programs.

Imagine a unique fingerprint for every person. Just like no two fingerprints are the same, the function mapping ensures that every distinct real number corresponds to a unique function, which further indicates the vastness of function sets over program sets.

So that is a very interesting theorem because generally we believe that using computers we can compute anything... There always exist tasks which you cannot compute or cannot compute or cannot find out their values you cannot solve those tasks using computers irrespective of how much time or how much memory you are allowed while writing down the program.

In this concluding chunk, we summarize the findings about uncomputable functions. The significant takeaway is the acknowledgment that there are inherent limitations to what computers can do—that not all mathematical functions can be computed, regardless of the time or resources provided. This serves to remind us that while computers are powerful tools, they are not omnipotent.

Think of a recipe that requires fantastic ingredients like 'a dash of imagination'. No matter how many ingredients you have at your disposal, you can't write a recipe for a dish that needs something you simply can't quantify, just like how some functions are beyond computation.

--