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:
print("Divisible")
else:
print("Indivisible")

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
print(a)

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.

Computer Science and Technology