We have already seen that a computer can do something that a Universal Turing Machine cannot do: generating a sequence of random numbers, which is completely unpredictable. We will now consider another example of the power of our computers: a way of stopping program loops. One of Turing’s results is to show that the problem of finding, for every program, whether it will loop or not is undecidable. However, it is possible to find loops in many programs. We will now use a capacity of computers for easily finding that a program is in an infinite loop.

Operating systems allow to use an interesting order: alarm N P. After N seconds, there is an interrupt: the computer gives the control to program P, whatever happens at that time in the computer. In CAIA, I called this program ZEUS: it can know everything about the present state of its own world, the computer. Then, it can decide to continue as if it had never stopped, or to change some data of the system before starting again, or to stop, or to start another task. Moreover, ZEUS can take another appointment in M seconds, and to store useful information on the state of the computer; the user, and perhaps later CIA itself, will possibly use it in the future for trying to find the reason of this loop.

The interrupt does not depend upon the CPU time, but upon the real time. One can use alarm as a timer: it gives a signal independently of what one is doing.

In order to be useful, ZEUS must first know what happened since the last interrupt. CAIA is built so that it stores all the interesting events, in such a way that there cannot be large amounts of time between two events: if there is no new event since the previous alarm, there is a strong presumption that CAIA is looping. The first time, it only modifies some parameters for inciting CAIA to create a more detailed record of its activities. Then, it restarts the task, being more attentive to possible anomalies. If it begins looping again, ZEUS gets once more out of trouble, and it will be still more cautious when it resumes this execution, or it will try another task.

A system must be able to observe its own state when there is an interrupt, consciousness is very convenient. This is precisely what CAIA can do, it is designed so that it knows all the running subroutines and the value of all their variables: in that way, ZEUS can know everything on the present state of the computer. Moreover, one can ask it to create a trace of the previous actions, which can be more or less complete. Therefore, ZEUS may know what led to the present state. If the trace is not precise enough, it can require a new execution of the same task with a more complete trace. When it loops again, it will have a better description of the past events. If ZEUS is still overwhelmed, CAIA can decide to stop the current task, and begin another one. Fortunately, it can give the user useful information, which will help him to find easily why the system loops. I have not yet given CAIA enough knowledge so that it can debug its programs by itself.

ZEUS is not only handy for finding useful information on loops, but it avoids wasting time in an endless loop. When I was leaving on vacation, I started a new life for CAIA, which was completely on its own. It would be a pity that it decided to stop after a few hours, or that it would endlessly execute the same 10 instructions for one month. Its autonomous lives always went extremely well.

I am using this method since 45 years. I had some false alarms: a task required much more time than expected. Nevertheless, I never had a system looping without being detected. Moreover, the system gives useful information for debugging the program.

The reason of this success comes from the use of real time by the alarm order. The number of instructions executed by the computer is independent from the time spent. A Turing machine cannot do this: it cannot access the real time.

As for the instruction giving a sequence of random numbers, the results found by Turing on undecidable problems always stand. This method only allows to find sometimes, but certainly not always, that a system will probably never halt. An interesting question is to ask ourselves whether other capabilities could be added to our computers, giving them possibilities that no Turing machine could ever have.

The main actor of a new film, The Imitation Game, is Alan Turing. This title is misleading: we could think that this film was based on the Turing test, although it is only referred in passing. In reality, this film is about Turing‘s part, during ww2, for decrypting Enigma messages. This film could be criticized for increasing the importance of Turing in breaking this unbreakable cipher. His part was essential, but other participants were also essential, and we can find little mention of them. Turing is almost absent in Robert Harris’ book on the same subject. Be that as it may, seeing this film is enjoyable.

This film is based on one of the three important results achieved by Turing: his role in breaking Enigma. The title reminds us of the second result, the Turing test. Here, I want to speak of the third result: the Universal Turing Machine.It is only implicitly mentioned in the film: Turing‘s commanding officer mentions that the title of one of his papers contains a word impossible to pronounce. Without any doubt, he refers to the word “Entscheidungsproblem“, which means “decision problem”. It appears in the title of his thesis, where he describes his machine. This word comes from the list of 23 mathematical problems published in German by Hilbert in 1900: it was the tenth one.

In his thesis, Turing states that his machine is limited: many problems are undecidable. This means that no general program can always find a solution for these problems. For instance, it cannot determine for any program whether it will ever halt, or print the number ’0′.

An interesting question is to determine whether this machine is as powerful as our modern computers. I am not interested in its efficiency: Turing Machine lacks many useful components, which can be simulated at the cost of a lot of computer time. For this theoretical machine, we are not interested in computer time, only in what it can do, no matter the elapsed time. It seems that Turing Machine is not more powerful than our computers: one can simulate its operations on a computer. However, although the tape used for storing symbols is finite, Turing assumes that his machine is always supplied with as much tape as it needs. Evidently, this is not true for our computers, but, given the size of their present memories, it is not very restrictive.

It is not so easy to answer the opposite question: are our computers more powerful than Turing Machines? As said before, we do not consider their efficiency, only whether a computer can perform some task impossible for a Turing Machine. I have found two of them, the first task being the computation of sequences of random numbers.

Random numbers are useful for many applications. They often allow to define a progressive scan of the search space effectively and efficiently. For instance, CAIA uses them for creating new problems. In these cases, it is not necessary to have “true“ random numbers, pseudo-random numbers are adequate. They are generated by an algorithm, which gives a sequence of numbers with the wanted dispersion properties.

However, for few applications, in games or cryptography, genuine random numbers are needed. This happens when a system has an opponent who must not be able to predict its future behavior. In this case, pseudo-random numbers may be hazardous: the opponent will foresee all the decisions taken by the machine if he knows the algorithm generating these numbers. Turing Machines can generate pseudo-random numbers, but they are unable to generate “true“ random numbers. Note that human beings are not very good when they have to generate random numbers.

Several researchers, around the year 1960, suggested to add an instruction that generated a random number each time it was executed. The idea was to use physical phenomena. This was not new, Mozart used dices for the random numbers, necessary for his minuet composition method. For the computers, they wanted to use the thermal noise of a vacuum tube. I do not remember if this idea was implemented, as random numbers were sufficient for most applications. Moreover, it would be very difficult to debug such programs. For the present time, RdRand generates random numbers, and it is supported by some CPU. Therefore, it is possible to have computers with “true“ random generators, and Turing Machines cannot do it.

The existence of this possibility does not destroy Turing’s results: with more unpredictable computers, solving the decision problem becomes evermore difficult.

In summary, our computers can perform a task that Turing Machines cannot do. Programs using “true“ random numbers have an interesting property: even if someone has such a program, and its data, he cannot simulate its future behavior. This can be very useful in all the situations where an opponent would like to foresee the forthcoming actions.

In a following post, we will see another situation where our computers have capabilities superior to those of Universal Turing Machines.