Hacker News Reader

Comment by wizeman | Hacker News Reader

> You asked if we could solve if it overflows a computer efficiently (without overflowing it), so I am showing that is not possible generally due to limitations of math; both our current understanding but also because math also has limits. (Gödel’s incompleteness theorem.)

What limitations of math exactly? What you're talking about is not related to efficiency of solving the Halting problem on a machine with a finite number of states.

> Attempting to overflow it is impractical using cpu cache memory sizes, no hard drive needed. No matter how fast you go through states, there are too many possible states in the cpu, and too many states even a small program can iterate through while still eventually terminating.

You are assuming that you have to simulate going through all the running states of a program to determine whether it halts or not.

Why do you assume that you have to run a complete simulation of the program to analyze it?

View on HN

Because some problems we lack the ability to solve any other way. There are at least three problems which are famous, as described in the article I linked.

see if you follow this one one, for a real computer:

Suppose I pick a n bit key, and encrypt a phrase with it. I will provide you the plain text phrase and either a real or fake cipher text. You have to determine if a program which loops through all the keys will decrypt the ciphertext into a the phrase.

Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase.

There is a relationship with proof of work crypto as well. Even all the Bitcoin mining has trouble finding hashes with a certain number of leading zeroes, add a few more zeros and no one will ever find a working seed again. There is no way to speed up the process beyond iterating over the seeds.

You can tie this to the halting problem by just saying to go back the key 0 once the key space is exhausted.

> Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase.

> There is a relationship with proof of work crypto as well. Even all the Bitcoin mining has trouble finding hashes with a certain number of leading zeroes, add a few more zeros and no one will ever find a working seed again.

Yup, I know. But here's the part I think you're missing:

None of those crypto systems you're mentioning are proven not to have weaknesses. In fact, weaknesses in hashing and encryption algorithms are encountered every now and then, even for those that have been considered state-of-the-art.

So yes, I agree that in practice we don't know how to solve this problem efficiently yet. Which means it's currently impractical, and would currently requiring brute forcing through all the states.

But I haven't seen a proof that it's not possible to find a practical algorithm.

There is no proof of that for our crypto systems. There is a proof you can’t prove ZF theory, but you also probably can’t prove it false. If you hide that question in the thing you iterate over, you can take it on faith you won’t find a counterexample and say the program won’t terminate; but you haven’t, and in fact cannot, prove it.

There are also lesser problems that have been around a while which we haven’t been able to prove, but might be provable… you can iterate over numbers looking for an counter example to the Collatz conjecture… I think that’s the best example of a simple program that is outside our current knowledge of math (better than the crypto one), but maybe someday we will have an answer.

Agreed!

Reply on news.ycombinator.com