12.4 Proving Non-Computability

We can show that a problem is computable by describing a procedure and proving that the procedure always terminates and always produces the correct answer. It is enough to provide a convincing argument that such a procedure exists; finding the actual procedure is not necessary (but often helps to make the argument more convincing).

To show that a problem is not computable, we need to show that *no& algorithm exists that solves the problem. Since there are an infinite number of possible procedures, we cannot just list all possible procedures and show why each one does not solve the problem. Instead, we need to construct an argument showing that if there were such an algorithm it would lead to a contradiction.

The core of our argument is based on knowing the Halting Problem is noncomputable. If a solution to some new problem $P$ could be used to solve the Halting Problem, then we know that $P$ is also noncomputable. That is, no algorithm exists that can solve $P$ since if such an algorithm exists it could be used to also solve the Halting Problem which we already know is impossible.

Reduction Proofs. The proof technique where we show that a solution for some problem $P$ can be used to solve a different problem $Q$ is known as a reduction.

A problem $Q$ is reducible to a problem $P$ if a solution to $P$ could be used to solve $Q$. This means that problem $Q$ is no harder than problem $P$, since a solution to problem $Q$ leads to a solution to problem $P$.

Example 12.1: Prints-Three Problem

Consider the problem of determining if an application of a procedure would ever print 3:

[ \textit{Prints-Three} ] Input: A string representing a Python program.
Output: If evaluating the input program would print 3, output True; otherwise, output False.

We show the Prints-Three Problem is noncomputable by showing that it is as hard as the Halting Problem, which we already know is noncomputable.

Suppose we had an algorithm printsThree that solves the Prints-Three Problem. Then, we could define halts as:

def halts(p):
   return printsThree(p +  '; print(3)')

The printsThree application would evaluate to True if evaluating the Python program specified by p would halt since that means the print(3) statement appended to p would be evaluated. On the other hand, if evaluating p would not halt, the added print statement never evaluated. As long as the program specified by p would never print 3, the application of printsThree should evaluate to False. Hence, if a printsThree algorithm exists, we would use it to implement an algorithm that solves the Halting Problem.

The one wrinkle is that the specified input program might print 3 itself. We can avoid this problem by transforming the input program so it would never print 3 itself, without otherwise altering its behavior. One way to do this would be to replace all occurrences of print (or any other built-in procedure that prints) in the string with a new procedure, dontprint that behaves like print but doesn't actually print out anything. Suppose the replacePrints procedure is defined to do this. Then, we could use printsThree to define halts:

def halts(p): return printsThree(replacePrints(p) +  '; print(3)')

We know that the Halting Problem is noncomputable, so this means the Prints-Three Problem must also be noncomputable.

Exploration 12.1: Virus Detection

The Halting Problem and Prints-Three Problem are noncomputable, but do seem to be obviously important problems. It is useful to know if a procedure application will terminate in a reasonable amount of time, but the Halting Problem does not answer that question. It concerns the question of whether the procedure application will terminate in any finite amount of time, no matter how long it is. This example considers a problem for which it would be very useful to have a solution for it one existed.

A virus is a program that infects other programs. A virus spreads by copying its own code into the code of other programs, so when those programs are executed the virus will execute. In this manner, the virus spreads to infect more and more programs. A typical virus also includes a malicious payload so when it executes in addition to infecting other programs it also performs some damaging (corrupting data files) or annoying (popping up messages) behavior. The Is-Virus Problem is to determine if a procedure specification contains a virus:

[ \textit{Is-Virus} ] Input: A specification of a Python program.
Output: If the expression contains a virus (a code fragment that will infect other files) output True. Otherwise, output False.

We demonstrate the Is-Virus Problem is noncomputable using a similar strategy to the one we used for the Prints-Three Problem: we show how to define a halts algorithm given a hypothetical isVirus algorithm. Since we know halts is noncomputable, this shows there is no isVirus algorithm.

Assume infectFiles is a procedure that infects files, so the result of evaluating isVirus('infectFiles()') is True. We could define halts as:

def halts(p):
   return isVirus(p + '; infectFiles()')

This works as long as the program specified by p does not exhibit the file-infecting behavior. If it does, p could infect a file and never terminate, and halts would produce the wrong output. To solve this we need to do something like we did in the previous example to hide the printing behavior of the original program.

A rough definition of file-infecting behavior would be to consider any write to an executable file to be an infection. To avoid any file infections in the specific program, we replace all procedures that write to files with procedures that write to shadow copies of these files. For example, we could do this by creating a new temporary directory and prepend that path to all file names. We call this (assumed) procedure, sandBox, since it transforms the original program specification into one that would execute in a protected sandbox.

def halts(p): isVirus(sandBox(p) + '; infectFiles()')

Since we know there is no algorithm that solves the Halting Problem, this proves that there is no algorithm that solves the Is-Virus problem.

Virus scanners such as Symantec's Norton AntiVirus attempt to solve the Is-Virus Problem, but its non-computability means they are doomed to always fail. Virus scanners detect known viruses by scanning files for strings that match signatures in a database of known viruses. As long as the signature database is frequently updated they may be able to detect currently spreading viruses, but this approach cannot detect a new virus that will not match the signature of a previously known virus.

Sophisticated virus scanners employ more advanced techniques to attempt to detect complex viruses such as metamorphic viruses that alter their own code as they propagate to avoid detection. But, because the general Is-Virus Problem is noncomputable, we know that it is impossible to create a program that always terminates and that always correctly determines if an input procedure specification is a virus.

Exercise 12.1. Is the Launches-Missiles Problem described below computable? Provide a convincing argument supporting your answer.

[ \textit{Launches-Missiles} ] Input: A specification of a procedure.
Output: If an application of the procedure would lead to the missiles being launched, outputs True. Otherwise, outputs False.

You may assume that the only thing that causes the missiles to be launched is an application of the launchMissiles procedure.

Exercise 12.2. Is the Same-Result Problem described below computable? Provide a convincing argument supporting your answer.

[ \textit{Same-Result} ] Input: Specifications of two procedures, $P$ and $Q$.
Output: If an application of $P$ terminates and produces the same value as applying $Q$, outputs True. If an application of $P$ does not terminate, and an application of $Q$ also does not terminate, outputs True. Otherwise, outputs False.

Exercise 12.3. Is the Check-Proof Problem described below computable? Provide a convincing argument supporting your answer.

[ \textit{Check-Proof} ] Input: A specification of an axiomatic system, a statement (the theorem), and a proof (a sequence of steps, each identifying the axiom that is applied).}
Output: Outputs True if the proof is a valid proof of the theorem in the system, or False if it is not a valid proof.

Exercise 12.4. Is the Find-Finite-Proof Problem described below computable? Provide a convincing argument supporting your answer.

[ \textit{Find-Finite-Proof} ] Input: A specification of an axiomatic system, a statement (the theorem), and a maximum number of steps (max-steps).
Output: If there is a proof in the axiomatic system of the theorem that uses max-steps or fewer steps, outputs True. Otherwise, outputs False.

Exercise 12.5. $\left[\star \right]$ Is the Find-Proof Problem described below computable? Provide a convincing argument why it is or why it is not computable.

[ \textit{Find-Proof} ] Input: A specification of an axiomatic system, and a statement (the theorem).
Output: If there is a proof in the axiomatic system of the theorem, outputs True. Otherwise, outputs False.

Exploration 12.2: Busy Beavers

Consider the Busy-Beaver Problem (devised by Tibor Rado in 1962):

[ \textit{Busy-Beaver} ] Input: A positive integer, $n$.
Output: A number representing that maximum number of steps a Turing Machine with $n$ states and a two-symbol tape alphabet can run starting on an empty tape before halting.

We use $0$ and $1$ for the two tape symbols, where the blank squares on the tape are interpreted as $0$s (alternately, we could use blank and X as the symbols, but it is more natural to describe machines where symbols are $0$ and $1$, so we can think of the initially blank tape as containing all $0$s).

For example, if the Busy Beaver input $n$ is $1$, the output should be $1$. The best we can do with only one state is to halt on the first step. If the transition rule for a $0$ input moves left, then it will reach another $0$ square and continue forever without halting; similarly it if moves right.

For $n = 2$, there are more options to consider. The machine in Figure 12.3 runs for 6 steps before halting, and there is no two-state machine that runs for more steps. One way to support this claim would be to try simulating all possible two-state Turing Machines.

Figure 12.3: Two-state Busy Beaver Machine.

Busy Beaver numbers increase extremely quickly. The maximum number of steps for a three-state machine is 21, and for a four-state machine is 107. The value for a five-state machine is not yet known, but the best machine found to date runs for 47,176,870 steps! For six states, the best known result, discovered in 2007 by Terry Ligocki and Shawn Ligocki, is over 2879 decimal digits long.

We can prove the Busy Beaver Problem is noncomputable by reducing the Halting Problem to it. Suppose we had an algorithm, bb(n), that takes the number of states as input and outputs the corresponding Busy Beaver. Then, we could solve the Halting Problem for a Turing Machine:

[ \textit{TM Halting Problem} ] Input: A string representing a Turing Machine.
Output: If executing the input Turing Machine starting with a blank tape would ever finish, output True. Otherwise, output False.

The TM Halting Problem is different from the Halting Problem as we defined it earlier, so first we need to show that the TM Halting Problem is noncomputable by showing it could be used to solve the Python Halting Problem. Because Python is universal programming language, it is possible to transform any Turing Machine into a Python program. Once way to do this would be to write a Universal Turing Machine simulator in Python, and then create a Python program that first creates a tape containing the input Turing Machine description, and then calls the Universal Turing Machine simulator on that input. This shows that the TM Halting Problem is noncomputable.

Next, we show that an algorithm that solves the Busy Beaver Problem could be used to solve the TM Halting Problem. Here's how (in Pythonish pseudocode):

def haltsTM(m):
   states = numberOfStates(m)
   maxSteps = bb(states)
   state = 0
   tape = []
   for step in range(0, maxSteps):
      state, tape = simulateOneStep(m, state, tape)
      if halted(state): return True
   return False      

The simulateOneStep procedure takes as inputs a Turing Machine description, its current state and tape, and simulates the next step on the machine. So, haltsTM simulates up to $bb(n)$ steps of the input machine $m$ where $n$ is the number of states in $m$. Since $bb(n)$ is the maximum number of steps a Turing Machine with $n$ states can execute before halting, we know if $m$ has not halted in the simulate before maxSteps is reached that the machine $m$ will never halt, and can correctly return False. This means there is no algorithm that can solve the Busy Beaver Problem.

Exercise 12.6. Confirm that the machine showing in Figure 12.3 runs for 6 steps before halting.

Exercise 12.7. Prove the Beaver Bound problem described below is also noncomputable:

[ \textit{Beaver-Bound} ] Input: A positive integer, $n$.
Output: A number that is greater than the maximum number of steps a Turing Machine with $n$ states and a two-symbol tape alphabet can run starting on an empty tape before halting.

A valid solution to the Beaver-Bound problem can produce any result for $n$ as long as it is greater than the Busy Beaver value for $n$.

Exercise 12.9. $\left[\star \right]$ $\left[\star \right]$ $\left[\star \right]$ Find a 5-state Turing Machine that runs for more than 47,176,870 steps, or prove that no such machine exists.