Hacker News Reader

It might only be wrong for programs that have never existed and will ever exist.

Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write. Well, to be fair, there is some upper bound for any program running on a real CPU.

>Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write.

We could confirm this though! It's not like we can't find out if a given program halts or is inconsisent. Godel talks about it in his letter to Von Nuemann.

There are programs for which we can check this, but there is no general procedure to check if any program halts. Even ignoring the halting problem itself, say we analyze a program and realize it halts iff P=NP, or pi to the e is transcendental, .or if Pi's decimal expansion at position Graham's number is divisible by 3. Will that program halt? It might be very hard to say.

More promisingly, there are ways to construct programs such they will halt, using total languages (though not every problem can be solved with such a limitation).

We can write a general procedure to see it any given program halts within n-steps however.

Reply on news.ycombinator.com