Diving Into The Abyss

Exploring the Unsolvable Halting Problem

As engineers, we often stand on the pedestal of mathematics, believing it to be the ultimate problem-solver. But what if we told you there's a problem so perplexing that even mathematics throws its hands up? Yes, you read that right. Let's embark on a journey into the world of the unsolvable: The Halting Problem.

A Brief Stroll Down The Memory Lane

Our exploration begins with two pioneering mathematicians, Wilhelm Ackermann and David Hilbert, who, before the 1930s, introduced the Entscheidungsproblem, or the "decision problem." This foundational problem sought an algorithm capable of providing a clear "yes" or "no" answer to any given input. Fast forward to 1936, and we encounter Alan Turing, a devoted mathematician who, while deeply immersed in the theory of computations, built upon this concept. Turing introduced the Halting Problem, a profound challenge that stemmed from the decision problem. Through his meticulous research, Turing revealed that there are specific problems, like the Halting Problem, which are fundamentally unsolvable. He posited that no machine can consistently predict whether it will halt or run indefinitely based on every possible input.

Turing Machines: The Basics

Before we get into the Halting Problem though, let's break down one of the prerequisites that will be required to understand the "proof", namely Turing Machines. Imagine:

1. An infinite tape for reading and writing.
2. A tape head scanning the tape.
3. A state transition table guiding the machine.
4. A state register tracking the machine's history.

Depending on the input, this machine either halts or runs indefinitely. To make it clearer, picture a Turing machine that flips binary input, as depicted in Figure 1.

The Halting Problem: A Paradoxical Genius

The clever man Alan Turing came up with this brilliant idea of proving that some things are just not provable *sighs*. In order to better understand how Turing proved the fact that some things are not provable let us think of a machine that could correctly identify whether a program will halt or continue running forever.

Lets consider a machine H, it takes in two inputs a w and an i. The w represents any program and i represents the inputs to w. Based on the program and the inputs to the program the machine will tell us whether this program will halt or not. Now let’s modify H so that it stops any program that is stuck in an infinite loop and if it stops it will make sure that it goes into an infinite loop. Now let us call this extended machine H+, now if we give H+ (the input and the program) to our original machine H, it cannot correctly identify whether the program will halt or not. The construction of this machine is shown in Figure 2.

Think of it this way, H is the original machine and H+ is the extended machine, now you give an input to the original machine and the original machine is supposed to check whether for a given program it halts or runs forever. The extended machine which is the H+ is supposed to make sure that every time the original machine halts, it forces the output to run forever.

In simpler terms: if for a given input the machine halts, the extended machine will force it to run forever and if it runs forever the extended machine will halt it. So for any given input, if the machine halts, the extended machine forces it to run forever and if the machine runs forever the extended machine forces it to halt, in short we’ll never know how the machine will behave like for these inputs.

This is where the paradox exists. So the initial premise that such a machine can exist which can correctly identify (on the basis of the input given to it) when the machine would halt or run forever.  Hence, the halting problem is not solvable. (As a side note, there's a whole set of rigorous mathematical statements that constitute the actual proof, but between reading that or this article, which one would you rather go through for now, eh?)

Wrapping Up

Computation, in any form, has its boundaries. The Halting Problem is a testament that some mysteries remain, regardless of our computational prowess.

If you've stuck with us till here, you might be yearning for a neat conclusion. But life, especially in mathematics, isn't always about neat endings. The Halting Problem is a gap, a challenge to logic. And while it might be unsolvable, it's a reminder that the journey of learning, with all its twists and turns, is what truly matters.

Did you like this explanation? click on the subscribe button below to get our latest blogs delivered directly to your email.