What if the halting problem solved!
What if | The geeks version
The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.
In 1936, Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. For any program f that might determine if programs halt, a “pathological” program g, called with an input, can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case.
Let’s get into it, I highly recommend watching this 6 min video before going any further. So, can we solve the halting problem? to answer this question, let’s consider the halting problem in a different way. A human being can raise his children, this is by nature. Looking at this special relationship between a father and his baby child, well, the baby is raised by his father. So, if we assume that the father is a function “h” where a father is a human being, this function, actually the father, takes as an input a baby child, let us call him small “x”, and map this baby to an output. What is the output of a father raising his baby? actually, the output is his baby being raised. Assume this baby child after being raised by his father is capital “X”. So, h(x) — > X is the relationship between a father and his child.
Now after we have defined this relationship between a father and his baby child who are both human beings, let us generalize a little bit. The function “h” is not just a father raising his child but, any human being can do so, then “h” denotes the relationship between any human and his baby child. let us take it a little bit further, a baby child is also a human being so, “h” would be the relationship between any human being raising another human being.
Having this relationship, let’s start asking questions. If a human being can raise a human being, can a human raise himself? known that it’s silly to tell, himself is also a human being? well, knowing that our logic is correct, we can say that a baby child can raise himself which is obviously not correct, although our logic seems to be correct. So, here is our first pitfall.
Let us move on and see whether our logic is wrong or the questions we ask. The next question is, can we find a long-living father, a human being, who can raise all children living now or will be given birth then? well, we know there isn’t but, assume we have one, a long-living human being father, following our logic, this relationship is absolutely correct. But can this long-living human being father raise himself !!. Well, a second pitfall.
Till now, every time we get to the point that seems our logic works 100% perfectly, the question “can he raise himself?” make it fails. Let’s be honest, we knew from the beginning that no one can raise himself, it’s like who comes first, the chicken or the egg, right?
Maybe we ask the wrong questions, maybe if we ask the right question we get a reasonable answer that conforms to our logic, let’s tweak it a little bit. Instead of asking “If there exists a human being who can raise all other humans?” we would ask “If there exists something that can raise all humans?”, would this make a difference? yes, of course, now we are not sticking to the point of being a human at all. So, what would be that something, I think you got this, you are right, it’s God, God can do so. But can God raise himself !!!!!!!!.
Back to the halting problem, what would be that something that can tell whether a program will or will not halt where its relationship to other programs will be as God to human beings. Does Alan Turing ask the right question? Can we ask like so questions? Let me know your thoughts.
