The Halting Problem

There are some problems computers just can't solve. Like why Starfishes are in star shape. Jokes apart, but here I am going to talk about one problem in particular known as The Halting Problem (Pretty cool name).

Before starting lets go back in time, to make thing more spicy !

David Hilbert (1928)

At the International Congress of Mathematicians held in Bologna, Italy, in 1928 mathematician and physicist David Hilbert returned to the second of the twenty-three problems posed in his 1900 paper Mathematische Probleme, asking

  • Is mathematics complete ?  (can we prove everything that's true)
  • Is it consistent ? (Does it give us none contradictory answers)
  • Is it decidable?

Three years later, the first two of these questions were answered in the negative by Kurt Gödel.

What about the third ? Lets talk about it later...

The Halting Problem

What is the meaning of Halting ?

Halt meaning in English is discontinue, terminate. Similarly, in Computer Science, Halting is the termination of programs.

Terminating (Halting) and Non-Terminating:

There are two types of computer program:
  • Terminating (Halting)
  • Non-Terminating
As the name suggests, terminating programs get terminated i.e. stops
for example
a = 5
b = 6
c = a%b
if c == 0:

This Program gets terminated after showing you the result. (Output depends on Input)

Now, about Non-Terminating, which simply means it goes on and on... i.e. infinite loop
for example:

a = 6
while a > 5 :
    a = a+1

Here "a" is always greater than 5 no matter what happens... and so it goes infinitely. (Output depends on Input)

But How did we decide that its an infinite loop ? 

  • By looking at the program and thinking about the possibilities
  • By running the program

What if there are 1000s or Millions or possibilities ? our brain just can handle that... so now the only way to check is to run it. But there is a problem here, What if the program runs for 10hrs and then gets terminated or if it gets terminated after 1 year or 2 or century ? Then its not a Infinite Loop.

Goldbach Conjecture
Can every even number greater than 2 be written as the sum of  two primes ?
Although every even number we encounter is the sum of two primes but we haven't come up with a way to prove it.

But what if, we wrote a computer program that went through all even numbers and ran an algorithm that checked all the different ways to write this number as two positive whole numbers x + y , when it finds two primes it moves to the next even number, if it fails to find two primes it terminates and prints a message.

If this Program ever gets terminated, so it will be proven that
Goldbach Conjecture is wrong. But as discussed above, How can we know if it ever gets terminated or not ?

Lets get creative now...

Can we write a program that can predict whether any other program and its Input will Halt or Run forever ?
Alan Tuning answer this in a very interesting way.

Let, f(x) be a program, that might determine that a program will halt or no. Let h(x) be another program who does the opposite of what f(x) determines i.e. if f(x) = halt , h(x) runs forever, and vice-versa

Let take another program g(x) as an input to f(x). h(x) does opposite of f(x) so h(x) would first need the output of f(x). So far so good !

Now, lets take h(x) as a input to f(x). Like before h(x) would need the output of f(x) so, if:

  • f(x) = halts then h(x) = run forever
  • Now h(x) = run forever ! so f(x) = run forever ! therefore h(x) = halt !
  • So if h(x) = halt at the same time h(x) = run forever... Lmao !
We reached an impossible contradiction. h(x) can't do both ! and Hence f(x) can exist !

And so we can't write a program that can predict if any other program and its input will halt or run forever.

And now about Hilbert's 3rd question.
Is Mathematics decidable ? and the answer is NO!


Popular posts from this blog

The Metaverse and Singularity