In other words, halting problem could be solved if we have sentient program which could intellectually interpret given code and say will it terminate or not (just like you as reader do with examples in the article).
Would you have known whether one of the examples returns true without knowing the Collatz conjecture (which was explained in the article)? And it’s a conjecture, we’re not sure it actually always works.
If you believe in encryption, no matter of intelligence can help you solve the halting problem. As in, if you believe the only way to decrypt some messages is to have the private key, then you will need to try a lot of keys to know if the following pseudocode terminates.
key = 0x0000...
while (decrypt(key, ciphertext) != plaintext) {
key++ // add 1, rollover to zero at the end of keyspace
}
return
The stars would burn out before anyone could answer this, without defeating the encryption algorithm.
As long as the number of keys is finite, you (or a computer) can still technically figure out whether your program will halt. The halting problem is semi-decidable and this is a case where you can decide, it just takes a long, long time. Moreover, in this case you can generally say “if one of the keys in the key space decrypts the message to the chosen plaintext, it will halt”.
The Collatz conjecture example on the other hand shows something where we don’t know whether it will halt for all input[1], because we don’t know if the Collatz conjecture is actually true. There are many other things without proof in either direction, some of which may not be able to be proven (Goedel’s incompleteness theorem says that if I’m not mistaken, but I am not a mathematician, please correct me if I’m wrong or inaccurate).
[1] Yes in practice the data types are limited, memory is limited, state in general is limited. So you can always “solve” the halting problem for a “real” computer by just trying out every representable state, even if that takes longer than the universe exists. But Turing machines, which is what the halting problem is defined on, have infinite tape.
Yes - this is true. A program will either halt or not, and if you could pluck that answer from somewhere, you would know.
But my point is in practice, this is just not possible, because the problem spaces are too large.
A related problem is the Busy Beaver Problem - how many steps can a program take as a factor of the number of turing instructions it contains. If we could determine that, we would "solve" the halting problem, in that we would know a program that is still running after N steps will never terminate.
However, even for very small programs, N is so large to be incomprehensible; ie, all the stars will have burned out even with all the compute in the world running until that happens.
And my point is that in general it’s not even possible in theory.
You brought an example for something where a particular instance is practically unsolvable (because you will run out of time). But it’s still possible to formulate an easy criterium for halting for that program, as I did above.
There are however programs where you can’t know if it halts or not for any input. No criteria can be made (apart from semi-decidable ones: “I know it doesn’t halt for x, does halt for y, but I still don’t know about z”). There is nothing where you can pluck the answer from, as you put it.
I’m pretty sure that isn’t true for real programs. The computer has a finite number of possible states depending on its physical properties or theoretical architecture - if you return to a state, there is a cycle and it will not terminate. Eventually it will hit the cycle or terminate.
No, the halting problem is not concerned with "the stars would burn out", and encryption is not useful for proving its undecidability. Framing the halting problem as "can we find the answer before the heat death of the universe" is not an interesting take: The program "count to g_64" [0] will run incomprehensibly longer than the universe will exist, but yet it trivially halts.
> In other words, halting problem could be solved if we have sentient program which could intellectually interpret given code and say will it terminate or not
This is wrong, and the proof of the halting problem illustrates why it must be:
Let's name your "sentient program" halts. That is halts(someProgram) "intellectually interprets" the code of someProgram and tells us whether running someProgram will terminate or not. Now consider the following program:
def g():
if halts(g):
loop_forever()
What is the value of halts(g)? Either option leads to a contradiction.
The article contains a few programs for which we (but also compilers nowadays) can statically determine whether they halt. This is not evidence of "intellectual interpretation solves the halting problem". It only means "there are programs for which we can determine whether they terminate", which does not in any way contradict "there cannot be a program that decides whether any arbitrary program halts eventually".
Halting problem assumes infallible machines doing the computation. The whole point is to show that there are things infallible machines can't reason about that humans can. It is however possible that a fallible computer could solve the halting problem.
>> Look, I’m not interested in solving your silly math problems. You said I exist, so while I don’t know if this function is true or not, I know I can figure it out and give you a yes or no answer.
Yep. The halting problem is semi-decidable, and this article showed a whole lot of “semi”. And an undecided one even, because Collatz is unproven (so we don’t actually know if that example really always works, and it may not be provable).
16 comments
[ 25.5 ms ] story [ 613 ms ] threadSomewhat sounds like an existential horror.
Are we such sentient programs?
Am I?
Hello?
The Collatz conjecture example on the other hand shows something where we don’t know whether it will halt for all input[1], because we don’t know if the Collatz conjecture is actually true. There are many other things without proof in either direction, some of which may not be able to be proven (Goedel’s incompleteness theorem says that if I’m not mistaken, but I am not a mathematician, please correct me if I’m wrong or inaccurate).
[1] Yes in practice the data types are limited, memory is limited, state in general is limited. So you can always “solve” the halting problem for a “real” computer by just trying out every representable state, even if that takes longer than the universe exists. But Turing machines, which is what the halting problem is defined on, have infinite tape.
But my point is in practice, this is just not possible, because the problem spaces are too large.
A related problem is the Busy Beaver Problem - how many steps can a program take as a factor of the number of turing instructions it contains. If we could determine that, we would "solve" the halting problem, in that we would know a program that is still running after N steps will never terminate.
However, even for very small programs, N is so large to be incomprehensible; ie, all the stars will have burned out even with all the compute in the world running until that happens.
You brought an example for something where a particular instance is practically unsolvable (because you will run out of time). But it’s still possible to formulate an easy criterium for halting for that program, as I did above.
There are however programs where you can’t know if it halts or not for any input. No criteria can be made (apart from semi-decidable ones: “I know it doesn’t halt for x, does halt for y, but I still don’t know about z”). There is nothing where you can pluck the answer from, as you put it.
FWIW, your take boils down to https://xkcd.com/1266/.
[0] https://en.wikipedia.org/wiki/Graham%27s_number
This is wrong, and the proof of the halting problem illustrates why it must be:
Let's name your "sentient program" halts. That is halts(someProgram) "intellectually interprets" the code of someProgram and tells us whether running someProgram will terminate or not. Now consider the following program:
What is the value of halts(g)? Either option leads to a contradiction.The article contains a few programs for which we (but also compilers nowadays) can statically determine whether they halt. This is not evidence of "intellectual interpretation solves the halting problem". It only means "there are programs for which we can determine whether they terminate", which does not in any way contradict "there cannot be a program that decides whether any arbitrary program halts eventually".
> That is a perfectly acceptable response.
No, it isn’t. Not all problems are decidable (https://en.wikipedia.org/wiki/Undecidable_problem)