Alan Turing |

**He is right, because the future is hardly predictable, but when it comes to quantum computing we tend to think that these computers, if they are viable, will let us solve problems quite different from those that can be addressed by the traditional computers to which we are used. In this context, however, mathematics can help us distinguish between what can be done, and what is completely impossible.**

*We are just in the beginning of some technologies that we still don’t know how far they will go.*
Although quantum computing is a fairly modern concept, its theoretical
foundation was established by Alan Turing during the 1930s. Let us review a
little of what he showed, for in this way we can correct a few optimistic ideas
spread by the media, often driven by

**who approach the issue from very different points of view, compared to Turing.***experts*
Alan Turing designed a special type of computing machine that, in his
honor, is called a

**. Although it isn't usually built with hardware, it is easy to simulate in an electronic computer. Essentially it consists of an***deterministic Turing machine***where one can write***infinite tape***, and a***symbols***that makes it possible to read and write them. The symbols the tape contains at the beginning of the process are the***head***of the machine, which is in a***input***chosen among a set of possible states. When it reads a symbol from the tape, the Turing machine writes another symbol in the same position, changes its state, and moves (or not) the head to read the symbol located in the next box, or in the previous one, or in the same. The machine is deterministic: when it is in a certain state and reads a specific symbol from the tape, its action is always the same.***state*A Turing Machine built with Lego |

**), which can simulate the operation of any other Turing machine if it is provided, as input, with the definition of the other machine (its state transition matrix) and with the input of the simulated machine. The universal Turing machine has a computing capacity equivalent to that of our traditional electronic computers, and was devised almost one decade before they were invented. Actually it’s even more powerful, for it’s supposed to have infinite memory. But this difference is now less important, considering the size of the memory of modern computers.**

*universal Turing machine*
On the other hand, Turing designed another type of computing machine,
the

**, which has the peculiarity that, after reading a symbol from the tape, it can perform several actions (go to several different states, writing different characters and move in different directions). The machine does not choose one among several possible actions, but performs all of them at the same time, in parallel. This machine is a good approximation of the quantum computers we are speaking about today, which at Turing time were unpredictable.***non-deterministic Turing machine***, which solves exactly the same problem (although much more slowly). An informal proof of this theorem can be found in section 2.3.1 of the book Teoría de Autómatas y Lenguajes Formales (Theory of Automata and Formal Languages, McGraw Hill 2007), which I wrote with my son Enrique and Professor Roberto Moriyón, to be used as a text in University studies on Computer Science.**

*he proved a theorem asserting that any non-deterministic Turing machine can be simulated by an equivalent determinist machine*
The consequence of this theorem is evident: quantum computers won’t be
able to solve new problems that up to now couldn’t be solved. Perhaps they’ll solve
quickly some problems that we can already solve with traditional machines,
although more slowly. Yes, some of those problems (called

**) take a long time to be solved (sometimes too much time) with the computers we use today, and maybe we’ll be able to solve them in a reasonable time with quantum computers, but solving new problems with them is totally excluded. Mathematics gives us the proof.***NP-complete*

*Problems which are undecidable using classical computers remain undecidable using quantum computers.***The same post in Spanish**

**Thematic thread on Natural and Artificial Intelligence: Preceding Next**

**Manuel Alfonseca**

## No comments:

## Post a Comment