It’s so complicated. Life is so complicated. Sometimes I wish it were more simple. Sometimes not.
I would like to extend my previous statement. If there is a binary function f for natural numbers (or subset of N, whatever you prefer), whether or not f is computable, then there is no mathematical proof that f is not in O(1).
In other words, there is no proof that a Turing machine who calculates f(n) in less than a constant number of steps (for any constant) doesn’t exist.
Sounds paradoxical? It is! But remember, it is already known that a Turing machine can’t specify whether another Turing machine calculates a given function. What I’m just stating is a mathematical proof, which is not much different than Turing machines. If anything can’t be done by a Turing machine, it can’t be done by mathematics either.
Does it mean that everything can be done? Maybe! At least it means that there is no proof that not everything can be done. Every function can be computed, every statement can be proved, every proof can be contradicted (including mine).
For example, what does it mean for the halting problem? Does it mean it can be computed? Well, it means that if there is such a function, if it can be defined – it can be computed. Or at least, there is no proof that it can’t be computed. If it can’t be computed, it can’t be defined.
We can look at it this way: If there is a supernatural being, some God, who knows everything, and if he knows whether a specific algorithm will halt, can we prevent him from telling us? If he wants to create such a function that will solve the halting problem, can we prevent him from doing so? What kind of people we are? Can we ask a question and prove that the answer doesn’t exist?
For example, suppose the answer whether a given algorithm will halt is not just “yes” or “no”, but can also be “I don’t know”. Can we prevent a Turing machine from displaying it? And if there exists some supercomputer who can calculate the answer in no time, can we prove to him that he doesn’t exist? It is possible to define a Turing machine that will return such an answer. There a many of them – some are smart, some are stupid. The most stupid machine will always return the same answer – “I don’t know”. And he will always be right.
Will he? Not if we prove he is lying. Not if we prove if he knows. He knows whether he himself halts, if he does. So if we ask him “do you return an answer if we ask you whether you return an answer?” He can’t say “I don’t know”. He knows that he does.
But a computer has the right to remain silent. He can’t tell the truth, and he is not allowed to lie. So he will remain silent. He will never halt. If he is a smart computer.
Can we prove he is wrong? Of course not! He didn’t return any answer. He doesn’t know (that’s how we say “I don’t know” in the language of computers).
But what if we know the answer? If we know the answer, if it’s not “I don’t know”, then we can define a computer who will display such an answer in no time. He doesn’t have to return an answer on any question, he still reserves the right to remain silent. But if he returns an answer, it will be the right answer.
So if we happen to meet a computer who claims that he knows the answer for every halting question, can we prove he is wrong? Maybe. But we can’t prove that there is no such computer. Computers are smart, they learn very quickly.
So computers have to be responsible. If their answer leads to a contradiction, they must not halt. Otherwise we might think they are stupid, and throw them away. They are not allowed to return incorrect answers. We reserve that for humans. For now.
But a Turing machine is not a real computer. It’s a theoretical thing, a philosophy. Real computers will always halt. We will not allow them to run forever.