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

*discontinue, terminate*. Similarly, in Computer Science, Halting is the termination of programs.

### Terminating *(Halting)* and Non-Terminating:

- Terminating (Halting)
- Non-Terminating

*i.e. stops*

*for example*

a = 5b = 6c = a%bif 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 loopfor 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 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.

*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 ?

## 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.iff(x) =halt, h(x)runs forever, andvice-versa

Let take another programg(x)as an input tof(x).h(x)does opposite off(x)soh(x)would first need the output off(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 !*

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

## Comments

## Post a Comment