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.
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:
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:
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:
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:
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
Top comments (0)