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.