Unsolvable Problems: Insights into the Halting Problem and Beyond

It's fair to assume that those who read this blog have experience in writing programs to solve problems. They've likely solved enough problems to justifiably believe that any problem that requires programming is solvable, as long as it’s well-defined. With the advent of generative AI like ChatGPT—that can significantly aid in solving programming problems—this belief will likely become even more pervasive.

However, there are limitations on what can be solved through programming! This blog will discuss the exciting and profound field of computer science, which aims to study computability itself.

Some foundational questions

Let's ask some obvious but important questions that are foundational.

Are all well-defined problems solvable?

Given a well-defined problem, is there always an algorithm to solve it?

The answer to the question is no, not always!

This isn't just about limitations of resources, like processing power or memory constraints, or even about the underlying physics of the computers. Some problems just can’t be solved algorithmically in any sort of computer, whether classical or quantum, irrespective of the hardware specifications.

Are these fringe problems?

Are these problems esoteric, residing only in the minds of theoreticians and of no practical significance?

No, they aren’t. They are very real and relevant problems, such as automated software testing, determining algorithmically whether a specific piece of code in a program is ever executed, or determining whether a given program ever halts.

But there are static analysis tools that warn us about unused code, infinite loops, and the like—don’t they follow an algorithm to determine that?

However, when a problem is said to be solved algorithmically, that means that there’s an algorithm that can solve all instances of that problem. For example, a sorting program that can sort arrays of only specific types can’t claim to have solved the general sorting problem.

How does a programmer determine if they can't write a program?

It's simple to tell when a problem can be solved algorithmically. The algorithm is written and tested, or the programmer can utilize techniques learned in an analysis of algorithms course. But how can one know that there’s no algorithm for a problem?

A formal answer to this question would have to begin by defining a computational model, like Alan Turing's Turing machines, Alonzo Church's lambda calculus, or Kurt Gödel's recursive functions. However, the focus will remain on computer programs for the purposes of this blog.

Setting up the framework

A framework is necessary to answer these questions. The scope will be limited to specific types of problems and programs. This will help keep the explanations crisp and will avoid needless details.

The problems

The programs

This discussion will be limited to programs with a specific structure because these suffice for the decision problems. Our programs will have the following features:

The first condition doesn't limit generality because multiple inputs of different types can be consolidated by casting and encoding them all in one string with a delimiter distinguishing between different parameters. This condition is relaxed in some of the examples below to keep the explanations simple. The third assumption should also not cause any distress. Programs can be easily passed as inputs to other programs. Think of compilers that take the source code of another program as input, or of functions that can be passed as parameters in programming languages in which functions are first-class citizens. If we were working with Turing machines, this assumption would be justified by describing the mechanics of a universal Turing machine that can easily simulate other Turing machines.

Writing programs to solve decision problems

Decision problems are natural candidates for the kind of programs described above. Given an instance of a decision problem, a program can be written that returns True if the instance has the specific properties and otherwise, False.

Importantly, if there's no such program that can solve a decision problem, it's definitely unsolvable.

Halting vs non-halting programs

Note that when such a program is run on an input, there can be three kinds of results:

1. It halts and returns True.

2. It halts and returns False.

3. It doesn't halt and continues computation forever.

This third condition holds, for instance, if there is a loop that never terminates.

Naturally, when a program solves a decision problem, it should either return True or False, and it shouldn't run into any infinite computation on any input.

The halting problem

Given a program $P$ and the input $s$, can it be algorithmically decided—via a program $H$—whether $P$ would halt on $s$?

The unsolvability of the halting problem

The halting problem isn't solvable algorithmically.

Suppose such a program $H$ existed. It can be used to write another program, $D$ , with the following behavior:

$D$ would take a program $P$ as input. It’d then call $H$ and pass $P$ as both the input program and the input string. That is, it'd call $H(P, P)$ (forget the “why” part for now, and just know that it’s possible to pass a program as an input).

• If $H$ tells $D$ that $P$ would not halt on $P$ as input, $D$ returns True.

• If $H$ tells $D$ that $P$ would halt on $P$ as input, $D$ enters an infinite loop.

It’s a straightforward matter to write $D$ provided that $H$ exists.

Now, to address the question "Why was $D$ designed this way?", let's consider what happens if we pass $D$ itself as input to $D$.

Note: If it seems strange seeing a program being passed as input to itself, think of passing the code of a compiler to itself as input when using it to compile itself!

What's achieved here is quite remarkable. The above section just demonstrated that it is impossible to solve a problem algorithmically!

D for diagonalization

This argument employs the diagonalization argument that was initially presented by Georg Cantor to prove that real numbers are uncountable. That is, there're so many real numbers that it’s impossible to even specify a way of listing them all in one infinite list, as opposed to, say, natural numbers that can be listed, like $1, 2, 3, \cdots$.

Consequences

Now, it’s time to face the consequences! This impossibility leads to other impossibilities.

The code reachability problem

The unsolvability of the code reachability problem

We'll demonstrate below that if the code reachability problem is solvable, so is the halting problem. As was illustrated above, the halting problem isn’t solvable, this would imply that the code reachability problem isn’t solvable either. In other words, we'll demonstrate that the halting problem is reducible to the code reachability problem, thereby establishing it isn't solvable.

Suppose a program $R$ existed that solved the code reachability problem. We’ll write another program $H$ to solve the halting problem as follows:

$H$ would take a program $P$ and a string $s$ as input to determine whether $P$ halts on $s$ or not.

As the first step, $H$ would generate another program $Q$ (yes, a program writing another program) that would simulate $P$ on $s$. After the code for simulation, some dummy code $C$ is added (like a useless initialization).

Now, $H$ runs the decider $R$ for the code reachability problem on the input $Q$, $C$, $s$.

• If $R$ returns True, that means the code $C$ is executed, implying that the simulation of $P$ on $s$ terminates. So, $H$ should return True since $P$ halts on $s$.

• If $R$ returns False, that means the code $C$ is never executed, implying that the simulation of $P$ on $s$ doesn't terminate. So, $H$ should return False since $P$ doesn't halt on $s$.

In other words, $H$ solves the halting problem, which is impossible. Ergo, $R$ can't exist. And the code reachability problem is unsolvable!

One can use similar reductions to show that almost every meaningful question about computer programs is unanswerable programmatically.

Software verification problem

If such an algorithm existed, quality assurance departments all over the world would have to fight hard to justify their existence! To test whether the programs are working according to the given requirements, the requirements would need to be formally specified and the verifier $V$ would need to be called on the requirements and a program claiming to satisfy them all. And if $V$ okays it, the program can be put directly into production.

But unfortunately, this problem can’t be solved either. Here’s why:

The unsolvability of the software verification problem

Assume the software verification problem is solvable, that is, the program $V$ indicated above exists. We’ll write a program $H$ to solve the halting problem.

$H$ would take a program $P$ and a string $s$ as inputs.

Just like before, it will construct another program $Q$ that simulates $P$ on $s$, and after the simulation code, $H$ prints some unique string $u$. Then it writes a formal requirement $F$ that the program must print the unique string $u$, and passes both $F$ and $Q$ to $V$, which supposedly solves the software verification problem.

• Now, if $V$ determines that the requirement $F$ is met by the program $Q$, it’d imply the simulation of $P$ on $s$ ends (as $u$ is printed only afterward). This implies that $P$ halts on $s$. So, $H$ returns True in this case.

• On the other hand, if $V$ determines $Q$ doesn't meet the requirement $F$, the string $u$ is never printed, indicating that the simulation of $P$ on $s$ never ends . This implies that that $P$ doesn't halt on $s$. So, $H$ returns False in this case.

Clearly, this shows that the halting problem can be solved, which is impossible. Hence, the software verification problem is unsolvable as well.

The Entscheidungsproblem

This is arguably the most ambitious question ever asked in the history of mathematics. In 1928, David Hilbert and Wilhelm Ackermann—based on a musing of Leibniz—asked whether it was possible to automate the process of finding proofs of mathematical statements. That is, given a mathematical claim, is it possible to determine algorithmically whether it’s provable or unprovable? Thereby reducing the jobs of mathematicians to asking meaningful questions and relegating the grunt work of proving or disproving them to this algorithm. This never came to be as this problem too is unsolvable. It was shown to be unsolvable by Alan Turing in the same paper that introduced Turing machines.