8.1. Definition of Computable and 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.

In this section, we discuss what computable functions are. A function 'f' is said to be computable if we can write a computer program that can calculate the value of 'f' for any valid input from its domain. This means that for every possible input value, the program should return an appropriate output value. It does not matter how long it takes or how much memory is used; the critical point is that a program exists to calculate 'f'.

Think of a vending machine as a computable function. You can input a specific code for a drink, and the machine will provide you with that drink in exchange for money. No matter how many drinks the machine can offer (even different codes), if you have the correct code, you can always retrieve your drink.

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 an uncomputable function. So as per the above definition, a function which is not computable will be called an uncomputable function.

Here we define uncomputable functions. A function is uncomputable if there is no program, regardless of resources like time or memory, that can compute it for every input. This means we cannot automate the calculation of its output through any conventional programming means.

Imagine trying to predict the exact future of a complex ecosystem purely based on current data. No matter how advanced your computer is or how much information it has, some outcomes may still be impossible to predict accurately due to the numerous unpredictable variables involved.

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.

The lecture proposes to prove that uncomputable functions exist by showing that while there are infinitely many programs, they cannot account for all possible functions. For instance, the set of all valid programs can be counted (enumerated) while the set of all functions may be larger, leading to uncomputable functions.

Think of a library. It has a certain number of books (valid programs). Now imagine an infinite collection of different stories (possible functions). While you can have an infinite number of stories, there aren’t enough books to hold them all if the library has a limited shelf space dedicated for them—this means some stories (functions) cannot be written down (computed).

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.

This segment explains the structure of valid programs that can be counted or enumerated. While it's possible to count valid programs, the number of potential functions between sets may vastly exceed this count. Thus, even with infinitely many programs, some functions remain outside their reach, establishing the existence of uncomputable functions.

Consider a recipe book filled with finite recipes (valid programs). Each recipe can produce a dish (function). No matter how many recipes are available, there are countless dishes that could exist (potential functions). This means that not every possible dish can be made with the recipes in the book, leading to 'dishes' that can't be easily created (uncomputable functions).

So our proof strategy will involve showing there exists at least one uncomputable function using a non-constructive approach.

In this part, the speaker introduces the proof strategy. The proof will be non-constructive, meaning instead of providing a specific example of an uncomputable function, it will logically demonstrate that at least one must exist. This type of proof is commonly used for existential statements, showing that the boundaries of computability are broader than initially perceived.

Imagine a treasure map leading to a single treasure chest with no boundaries specified—only the existence of the treasure is acknowledged. You're not given where it is but are told it exists. The treasure is akin to finding at least one uncomputable function that cannot be explicitly identified but is proven to exist through logical reasoning.

We will show that the cardinality of this collection of all possible functions is not א0.

In this section, the aim is to show that the number of possible functions (from the set of positive integers to digits) is more than the count of valid programs. This is crucial because if valid programs (countable) are fewer than possible functions (which could be uncountable), it logically leads to the conclusion that uncomputable functions exist.

Picture trying to match every student (valid programs) in a school to every type of music they might enjoy (possible functions). If there are more music genres than students, inevitably, some music genres will not find a student who likes them. This scenario mirrors why some functions remain uncomputable—they simply do not have the right program to compute them.

--