The Halting Problem

Using quantum mechanics, the proven impossible may have become possible.

Let’s say I gave you a computer program. You have one simple job: tell me whether the program will go on forever or stop. Give it a try with the Java program below. If you don’t know Java, you can read the text that follows the “// to understand what each line does.

The program will continue to print “Hi!” as long as x remains one. Because x stays one, the program will indefinitely print “Hi!”. How about this program?

This one is a bit harder. If you arrived at the solution to this problem, congratulations!!! This problem has remained unsolved for nearly three centuries. This is the Goldbach conjecture, which states that every even number greater than two can be written as the sum of two prime numbers.

The computer program above loops through every even number greater than two and verifies whether the program can be expressed as the sum of two prime numbers. If the program finds a case that contradicts the Goldbach Conjecture’s conditions, the program stops. If we could know whether this program stops or not, we would solve the Goldbach conjecture. There’s just one problem. The “simple” task I just assigned you has stumped mathematicians for decades because it was proven impossible.

The Halting problem, first theorized by Alan Turning in 1936, asks if there exists an algorithm that takes an input of a computer program and outputs whether the program will run forever or halt. If the Halting problem were solved, many other unsolved problems, such as the Busy Beaver Function, the Kolmogorov Complexity, and the Collatz Problem could be answered as well by creating programs similar to the Goldbach Conjecture program and determining whether the program would halt or continue forever. 

However, Turing was able to prove why such an algorithm could never exist by contradiction. The Halting problem is among the first problems with a proof deeming it unsolvable. The proof goes as follows:

Let’s say that an algorithm that determines whether a program halts or not exists. This algorithm’s name is Halt, and it takes two inputs: the program (X) and its input (I). Based on these inputs, this algorithm will output “halt” or “runs forever.” Using the Halt algorithm, let’s create a second algorithm called Opposite which takes in a program (Y) for its input. This algorithm runs the Halt algorithm by making Y both of Halt’s inputs. The output of Halt becomes the opposite action of Opposite. If Halt returns “halt,” Opposite will run forever and vice versa. These programs appear to run smoothly until we input Opposite into itself. The Halt algorithm has two options it can output. If it outputs “halt,” Opposite will run forever, making the Halt’s output incorrect. Similarly, if Halt outputs “runs forever,” Opposite will halt. Because the Opposite algorithm can’t run forever and halt at the same time, by contradiction, the Halting problem will never be solved for all cases.

Several months ago, however, a group of researchers proved that quantum computers may make the Halting problem possible.

Quantum computers operate similarly to standard computers, but the method for storing data is slightly different. Standard computers store information using bits, a unit of data that can be either a zero or a one. Quantum computers, on the other hand, store their information using qubits which can be a combination of both zero and one. (See this article for a further, in-depth explanation of how quantum computers operate).

Another version of the proof involves interrogation. If you have a suspect in a crime, you may not know whether they committed the crime. As the person with the information, the suspect will be called the prover; as the interrogator, you will be the verifier. By asking the suspect certain questions, you could find your answer. 

When two provers are introduced, the ability to gain information becomes easier. Now, instead of one suspect, there are two suspects. Because you have two provers, you could use your questions to catch the provers in a lie. With one prover, you had to blindly take your interrogator’s word.

A similar concept applies to computers. Let’s take two computers. The more knowledgeable computer will be called the prover, and the questioning computer will be called the verifier. The verifier can ask the prover certain questions to gain access to the information the prover has, allowing the verifier to gain access to knowledge beyond its individual scope.

Quantum entanglement is a concept where the properties of two particles are linked. By measuring a property in one of these particles, you can gain information about the other particle. When one particle changes, the other particle does as well. If the two provers were entangled, it may seem as though it would be easier for the provers to lie, but entanglement actually makes lying harder. Take the example of the following riddle:

You are at a crossroad where there are two paths. One path leads to your favorite place in the universe, while the other path will teleport you to the opposite side of the universe. You have to choose a path. Fortunately, there are two twins who know what the destination of each path is. You are permitted to ask them one question, but you do know something about these twins. One twin only lies, whereas the other twin only speaks the truth. You have no idea who is whom, so what question do you ask that will lead you down the path to your favorite destination?

The answer: which path would your twin say is the path to your favorite destination? The lying twin knows that his truth-telling twin would respond with your favorite destination, so the lying twin points towards the path leaving you lost forever. The truth-telling twin knows that his twin would lie about your favorite path and respond with the path that makes you lost. Obligated to tell the truth, this twin responds with the path that would make you lost as well. By going on the opposite path, you would end up going down the right path. Without knowing which twin told the truth and which one lied, you would find an answer to a problem beyond the scope of what you knew. By asking quantum entangled particles the right questions, they may be able to answer unsolvable questions, including the Halting problem. 

Through the powerful technique of interrogation with entangled particles, we will be able to understand concepts that seemed unthinkable to us. By potentially solving the Halting problem using quantum entanglement interrogation, a domino effect of resolving the many unsolved problems of our world may follow. At that point, there is no halting us.

– Anjali Reddy