### 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:
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.

## 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.