Aided by artificial intelligence technologies, computers can now have persuasive conversations with humans, compose songs, paint paintings, play chess, and diagnose diseases, to name just a few examples of their technological capabilities.
These achievements could be taken as an indication that there are no limits to computation. To see if that’s the case, it’s important to understand what makes a computer powerful.
There are two aspects to a computer’s performance: the number of operations its hardware can perform per second and the efficiency of the algorithms it performs. Hardware speed is limited by the laws of physics. Algorithms—basically sets of instructions—are written by humans and translated into a sequence of operations that computer hardware can perform. Even if a computer’s speed could reach the physical limit, computational hurdles remain due to the limitations of algorithms.
These hurdles include problems that are impossible for computers to solve and problems that are theoretically solvable but in practice are beyond the capabilities of even the most powerful versions of today’s computers imaginable. Mathematicians and computer scientists try to find out if a problem is solvable by trying it out on an imaginary machine.
An imaginary calculating machine
The modern notion of an algorithm, known as a Turing machine, was formulated by British mathematician Alan Turing in 1936. It is an imaginary device that mimics arithmetic calculations done with a pencil on paper. The Turing machine is the template on which all computers are based today.
To account for calculations that would require more paper manually, it is assumed that the supply of imaginary paper in a Turing machine is unlimited. This corresponds to an imaginary boundless band or “band” of squares, each of which is either empty or contains a symbol.
The machine is controlled by a finite set of rules and starts with an initial sequence of symbols on the tape. The operations that the machine can perform are moving to an adjacent square, deleting a symbol, and writing a symbol to an empty square. The machine calculates by performing a sequence of these operations. When the machine finishes or “stops”, the symbols remaining on the tape are the output or result.
Arithmetic often involves decisions with yes or no answers. Similarly, a medical test (type of problem) checks whether a patient’s sample (an instance of the problem) has a specific disease indicator (yes or no answer). The instance, represented in digital form in a Turing machine, is the initial sequence of symbols.
A problem is considered “solvable” if a Turing machine can be designed that stops for each positive or negative instance and correctly determines which answer the instance returns.
Not every problem can be solved
Many problems are solvable with a Turing machine and can therefore be solved on a computer, many others cannot. For example, the domino problem, a variation of the tile problem formulated by Chinese-American mathematician Hao Wang in 1961, is unsolvable.
The task is to cover an entire grid with one set of dominoes and, according to the rules of most domino games, match the number of dots at the ends of the dominoes that abut. It turns out that there is no algorithm that can start with a set of dominoes and determine whether the set completely covers the grid or not.
keep it reasonable
A number of solvable problems can be solved by algorithms that stop in a reasonable amount of time. These “polynomial-time algorithms” are efficient algorithms, which means it’s convenient to use computers to solve instances of them.
Thousands of other solvable problems are not known to have polynomial-time algorithms, despite ongoing intense efforts to find such algorithms. This includes the problem of the traveling salesman.
The traveling salesman problem asks whether a set of points with some directly connected points, called a graph, has a path that starts from any point and goes through every other point exactly once and returns to the original point. Suppose a seller wants to find a route that passes all the households in a neighborhood exactly once and returns to the starting point.
These problems, referred to as NP-complete, were formulated and proved independently in the early 1970s by two computer scientists, Canadian Stephen Cook and Ukrainian Leonid Levin. Cook, whose work ranked first, received the 1982 Turing Award, the highest in computer science, for this work.
The cost of accurate knowledge
The most well-known algorithms for NP-complete problems essentially search for a solution from all possible answers. The traveling salesman problem on a graph with a few hundred points would take years to run on a supercomputer. Such algorithms are inefficient, meaning there are no mathematical shortcuts.
Practical algorithms that address these problems in the real world can only offer approximations, although approximations are improving. Whether there are efficient polynomial-time algorithms that can solve NP-complete problems is one of the seven millennial open problems published by the Clay Mathematics Institute at the turn of the 21st century, each endowed with a million dollars.
Beyond Turing
Could there be a new form of computation beyond Turing’s framework? In 1982, the American physicist Richard Feynman, a Nobel Prize winner, put forward the idea of computation based on quantum mechanics.
In 1995, Peter Shor, an American applied mathematician, presented a quantum algorithm for factoring integers in polynomial time. Mathematicians believe this is unsolvable by polynomial-time algorithms in Turing’s framework. Factoring an integer means finding a smaller integer greater than one that can divide the integer. For example, the integer 688,826,081 is divisible by a smaller integer 25,253 because 688,826,081 = 25,253 x 27,277.
An important algorithm called the RSA algorithm, widely used to secure network communications, is based on the computational difficulty of factoring large integers. Shor’s finding suggests that if quantum computing becomes a reality, it will change the cybersecurity landscape.
Can a full-fledged quantum computer be built to factor integers and solve other problems? Some scientists believe this may be the case. Several groups of scientists around the world are working to build one, and some have already built small quantum computers.
Still, as with all novel technologies invented before, there will almost certainly be problems with quantum computing that would set new frontiers.
This article was republished by The Conversation under a Creative Commons license. Read the original article.
Credit: Laura Ockel/Unsplash
