Hacker News Reader

Comment by swid | Hacker News Reader

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.

View on HN

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.

FWIW, your take boils down to https://xkcd.com/1266/.

[0] https://en.wikipedia.org/wiki/Graham%27s_number

Reply on news.ycombinator.com