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.