8.2. Proof Strategy for Existence of 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. 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.

This section defines computable functions in the context of programming. A function is considered computable if a program exists that can calculate its output for any input from its domain. The focus is not on how fast the program runs or the resources it uses, but rather if such a program can be created at all. If no such program can exist to compute the function for every input, it is labeled as uncomputable.

Think of a recipe as a function. A computable recipe means you can follow the steps to consistently produce the dish every time (like a program running correctly). An uncomputable recipe, on the other hand, would be one where, no matter how hard you try, the steps make no coherent dish (like trying to compute something with no possible program).

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.

The lecturer intends to show the existence of uncomputable functions, asserting that no matter the resources available (time, memory), there will always be functions that cannot be programmed. The proof strategy starts with a known fact: all valid programs in a programming language are countable, meaning we can create a list of them, even if it is infinite. Valid programs are defined as those that have a clear start and end, and can produce outputs.

Imagine trying to create a library of all books written in a particular language. If every potential book were counted, we'd realize there are many more stories to tell than books ever written. Similarly, the library of computer programs can be large, but there will always be stories (functions) that have never been told, representing uncomputable functions.

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.

The text explains that each program can only compute one function from the collection of all possible functions. Thus, no single program can compute two different functions since their definitions and outputs will differ. This leads to the conclusion that there exist functions that cannot be computed by any program on our list, further supporting the existence of uncomputable functions.

Consider a custom gadget designed to perform a specific task, like making ice cream. If you had another gadget designed to make juice, the ice cream machine wouldn't be able to make juice and vice versa. Each gadget (program) has a unique task (function) it can perform, reinforcing that not every task can be handled by a single gadget or program.

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.

The text discusses the nature of the proof being argued. This is a non-constructive proof, which is a type of argument used to demonstrate that something exists without showing a specific example. Here, the claim is that at least one uncomputable function exists, and while an exact function isn't specified, logical reasoning suggests such a function must exist.

Imagine you are told there is a treasure hidden in a vast jungle. No one gives you the exact location (a constructive proof), but they provide reasoning based on ancient maps that such a treasure exists. You become convinced of its existence purely based on the logical explanations, similar to how a non-constructive proof works.

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.

The lecturer summarizes the proof: there are more functions than computable programs available, leading to the existence of uncomputable functions. Since every program corresponds to a single function, if the number of functions exceeds that of the programs, it confirms some functions are uncomputable. This serves as a reminder that not everything can be computed by machines.

Consider the limits of a car's speed—as it can only go so fast and thus can't reach every destination in an instant. In a similar way, while computers and programs can perform countless calculations, they cannot solve every possible problem effectively or find all outputs, revealing limitations in computation.

--