In the last lecture, we discovered some shocking news. It appears that there is a physical limit for the current computing technology. At some point, we will not be able to construct a smaller transistors and the growth of our computing power will eventually stop. This along can distress us, but there's more. I already mentioned the word universality. Now, it's time to dig a little bit deeper, understand what does it mean. To do that, we first need to define what is the goal of computation. Computation transforms information. That's true. But why? Can we give a general answer to this question? Yes, we can. If you reflect a bit on any computation you ever performed in your life, you will probably agree that you computed the value of some function. Again, it is just another way of saying that computation transforms information because it maps some input data to some output data and so does any function. So, why do I need this another definition? Why do I need to employ this notion of function? Because functions have a strict mathematical definition. I can define, for example, the whole set of functions which transform natural numbers, map actual numbers to one bit. This set is infinite, but it is well defined. Now, I can ask myself, if I can compute any of these functions. For this question to be correct, I have to define first what does it mean that I can compute a function. For example, for a function f, I can compute it that if for any x, natural x, I can compute f of x, but there's an infinite number of such inputs. So, how can I be sure that I can do that for any of them? I can be sure if I have an algorithm for computing this function. But again, I just explained one clear thing through another. What is algorithm? The answer to this question was given by the English mathematician, English scientist, Alan Turing in his PhD thesis in 1936. Algorithm is deterministic Turing machine. Before that definition, there was some understanding that algorithm is something which works for any input data, it has infinite number of steps and it requires no thinking effort. But Turing gave us this strict mathematical definition. So, algorithm is deterministic Turing machine, DTM and it is as you probably remember, is infinite tape market into squares and infinite alphabet, symbols of which can be written on these squares and read-write tape which can read and write one symbol at time on each step and infinite number of states, including the initial state and final states and infinite number of rules which control the behavior of this abstract model. So now, algorithm is a finite tuple of finite set and sets elements. This is a very powerful model because it allows us to define the universal Turing machine, which is the deterministic Turing machine, which accepts another Turing machine as it's simple and emulates it's behavior. So, this universal Turing machine can do anything that any other deterministic Turing machine can do. There are the time in 1936, a hypothesis was from weighted which is now known as Church-Turing Thesis, which states that there is no other deterministic computing device if the report are larger than that of deterministic of the universal Turing machine. So now, this question, if we return to the question of computability, now this question about these functions, which transform natural numbers to one bit. Now, this question makes sense. We can ask ourselves, if all these functions are computable and we can try to reply to this question. So, are they computable? Because for any function to be computable, now it means that there is a deterministic Turing machine which computes this function. To answer this question, we first, we'll count how many deterministic Turing machines are up there. Of course, it is an infinite set, but we are going to find out which is the cardinality of this set. Since any deterministic Turing machine is a finite tuple of finite sets and elements, it can be encoded as a finite string in some alphabet. For example, in the alphabet of ones and zeros. So, any deterministic Turing machine, we can represent like this. Some finished string of zeros and ones. Any of such strings can be mapped to two natural numbers. First is the number of leading zeros and the second is the number represented by this string in binary encoding. This set is countable, so now, we can conclude that we have only a countable infinity of deterministic Turing machines. Sounds good. Now, let's compute how many functions of this type are there. To do this, we are going to define the following procedure. I will take some function from this set. For this function, I am going to write a string, again of ones and zeros. I'm going to write one, zero, then there's no comma. Then, I'm going to write one bit, which is f of one. The next bit is f of two, f of three, etc., up to infinity. This infinite string of ones and zeros represents some real number on the interval from zero to one and different functions map to different numbers from this interval and different numbers from this interval defined in this way, different functions. We perfectly know that there are continuum of such numbers, of real numbers on the interval zero, one. So, there is continuum of these different functions of this step, which means that there are uncomputable functions. Even more if we take a function from this set at random, then the probability of the event we can compute it is zero. We can compute almost nothing in this mysterious and beautiful world. Okay. Maybe it's not so bad. Maybe all these uncomputable functions are bizarre and useless. It appears to be not true. In the same paper where Turing defined this deterministic Turing machine, he provided us an example of a very useful function, which is uncomputable and this example is now known as the halting problem. Mention a function, for example, we'll call it H, which the deterministic Turing machine, some algorithms as its input and the input for this deterministic Turing machine. This function returns zero if this machine will stop, will eventually stop on this inputs at some point of time and provide us some result. It returns one if this Turing machine hangs on this input. So, for this input, it has some infinite loop. So, this function H, it analyzes in some way the machine on its input and gives us an answer if it has an infinite loop for this particular input or if it does not. Turing proved and this is a quite an easy proof that this function H is uncomputable. So, it means that deterministic Turing machines cannot analyze deterministic Turing machines. If Church-Turing thesis is correct, then we're deterministic Turing machines and we are not able to analyze every computer program, which means that there can exist, can be written a computer program which we will not be able to understand or to predict its behavior at deterministic computing computer program. Isn't that amazing?
