Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

He proved that any sufficiently complex math system will have unprovable sentences.

That's mostly because "sufficiently complex" is defined by mathematicians, not computer scientists. In particular, it includes infinities, which do not exist in the physical universe. Godel's proof requires allowing unlimited depth recursion, which does not exist in the physical world.

The halting problem is decidable for any deterministic system with finite memory. Either you halt, or you repeat a state. This covers most real-world computer programs.

There's a useful subset of arithmetic and logic which is completely decidable. It contains integer addition, subtraction, multiplication by constants, and all the logic operators. This covers most subscript checking in programs, which is quite useful. You can probably add modular arithmetic with a fixed upper bound to that subset.

Now, some systems may require very large amounts of work to prove, but that's different from being undecidable. "Very large" is not infinite. That heads us off into the theory of lower bounds, P = NP, and all that, where there are still many open questions.

This knocks out many of the sillier claims about undecidability making something impossible in the real world.




>In particular, it includes infinities, which do not exist in the physical universe.

Bold claim. As far as I know the centers of black holes are indeed non-removable singularities of (some) solutions to GR equations.

What's funny is I had a debate with a cosmologist where I was on your side of the debate because he was a mathematical realist (and therefore forced to reconcile the same divergences with the "reality" of math).


> The halting problem is decidable for any deterministic system with finite memory. Either you halt, or you repeat a state. This covers most real-world computer programs.

Problem being that you cannot decide whether a system with such finite memory halts without using another different system that has even more memory. And if that larger system doesn't "real-world" exist, can you truly say that the halting problem is decidable?


You can determine if a program halts by running two copies in lockstep, one at half the speed of the other. If their states are ever the same after the first step, they're in an infinite loop.

That was actually used in an early batch system for running student jobs in an interpreter. A successful student job ran for under a second; one in a loop ran for 30 seconds until it was killed for taking too long. So detecting simple loops, even with substantial extra overhead, was worth it.


Yes, but the point is, if you have an amount of memory M, there exists an amount of memory N for which there is no program that fits into M that can successfully predict whether an arbitrary that fits into N will halt. No infinites required.

(since your example is using two copies, you're essentially using 2M memory)


Exactly!

For the same reason, when someone uses halting problem to 'explain' why their program freezes, they are wrong. They are wrong on multiple counts actually.

For pure mathematics, this stuff is relevant. For all practical purposes, it is not (as far as infinite-precision analog memories are not involved).




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: