Halting Problem, the undecidable problem for Turing machines...
Tags: computerscience, algorithms
Published: 2021-07-29 14:42:10

In 1936, the Englishman Mathematician, Alan Turing invented a machine called the Turing machine, Turing machine is a model of computation that's able to manipulate the symbols on a tape as a series of defined rules, the machine header will move over the cells of the tape which can read‌ and write symbols on the cells of the tape based on its given instruction.

![turing machine tape](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j7mdy34dxggbymsptykz.png)

With the help of the Turing machine, we are able to solve any computational problems that have the ability to define mathematically.

But wait a second! Did we say any problem? Well, no... there are some undecidable problems like the subject of this article that is the Halting problem and the NP-Hard one!

## Halting Problem:
Halting Problem is a decision problem, in summary, that mean we have to answer that by true or false, yes or no.
e.g:
```rust
fn is_odd(x: i32) -> bool {
    return x % 2 != 0
}
```
The halting problem is about determining that if we give a value to a machine, that will halt or will be looping forever, in the following, i will explain it in a straightforward way...


## Proof:
as we said our goal is to develop a machine/algorithm that should recognize what happens if we execute an arbitrary program with a specified value, it will halt or will be stuck in an infinite loop.
in this example we will consider there is a `willHalt` function that will tell us the given program will halt with the given value or not! (**this is merely an assumption**)
this is somehow a sample code:

```js
const willHalt = (cb, value) => (cb(value) === "Halt" ? true : false);
```
okay, now we want to create an arbitrary program that will prove that the `willHalt` program can't exist, by creating a paradox!

there is a program called `arbitraryProgram` that takes a parameter as input and then executes the `willHalt` program with its own input value, (**if**) the `willHalt` returns true, an infinite loop will be executed, otherwise the **Halt** value will be returned, and here is another sample code:

```js
function arbitraryProgram(value) {
  if (willHalt(value, value)) {
    while (true) {}
  } else return "Halt";
}
```
what do you think will happen if we run the `arbitraryProgram` function with itself as input like this `arbitraryProgram(arbitraryProgram)`?
infinite recursion...? No! **as we said earlier, we will consider that the `willHalt` function will tell us the correct answer the first time.**

take a look at this flowchart:
![flowchart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/02za6xm5cb0zmrl4oujg.png)

as you see in flowchart the problem is the `arbitraryProgram` function, let's check it out...

-> if `willHalt` function says "true", an infinite loop will be executed, then our program will stuck in an infinite loop! the `willHalt` answer is wrong!

and in another mode:

-> if `willHalt` function says "false", the `arbitraryProgram` will stop by returning a value, and again the answer of `willHalt` function is wrong...
and this proves us the `willHalt` function can not exist!

but what if we don't assume that the `willHalt` function works finely? simple! tjat will contiue running forever until the call stack has reached its maximum limit!
.
.
.
.
.
the halting problem is just one of the undecidable problems, if you are interested in these type of issues, there are other problems such as **Entscheidungsproblem** that you can research about it.

if this post was helpful, share it with others... tnx.

research resources:
https://www.youtube.com/watch?v=wGLQiHXHWNk
http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/TM.pdf
https://www.quora.com/What-is-the-difference-between-Entscheidungsproblem-decision-problem-and-Halting-problem