With the invention of the Turing machine came the revolutionary concept that it could solve all computable problems. In evidently came The Halting Problem.
Instead of saying that a program does not exist or can never exists to compute a certain thing, computer scientists would say," The halting problem is not solvable.”
What is the halting problem?
Almost all programs created using one of the many assembly languages out there, use loops or some sort of recursive function. It just makes life easier and some programs can simply not work without loops.
Scientists wanted to know if a program exists that can determine whether all the other programs will terminate if its Gödel Number represents it.
A Gödel numbering can be interpreted as an encoding where a number is assigned to each symbol of a mathematical notation, and a stream of natural numbers can then represent some form or function. A numbering of the set of computable functions can then be represented by a stream of Gödel numbers (also called effective numbers). Rogers' equivalence theorem states criteria for which those numberings of the set of computable functions are Gödel numberings.
Thus the halting problem was born.
The proof behind the halting problem!
Scientists use a contradiction to prove that the problem is not solvable. An informal proof starts of where we assume a program, Test, exists. As input, it takes any program, for clarity purpose let us call this program P, represented by its Gödel number.
The Test program will then either output “1” if P terminates and it will output “0” if P does not terminate.
Moving on to Step 2. Create another program called Q.
Q will consists of an empty body loop and will use Test’s output as input.If P terminates, thus giving us a “1” as input to Q. However, here comes the interesting part. The loop inside Q will not terminate if the input to it is “1”, creating an infinite loop and if the loop does not terminate then Q cannot terminate.
If P provides input as a “0” to Q then the body of the loop never iterates meaning Q can terminate.
The last part of the proof involves testing Q with itself.
Using Q’s Gödel number as input to Q. This can be done only because we did not put any restrictions on program P. To make the next part of the explanation easier we will call the input Q1 and the testing program Q2.
Assuming that the program, Test, exists the following contradiction occur:
- Q2 does not terminate if Q1 terminates.
- Q2 terminates if Q1 does not.
The halting problem has made it easier to prove other programs cannot exist, because if they exist, the halting problem exists, which we just established cannot happen.
Sources
https://simple.wikipedia.org/wiki/G%C3%B6del_numberhttps://en.wikipedia.org/wiki/Halting_problem