Hacker News new | ask | show | jobs
by Verdex 929 days ago
No.

Godel means that we can't have an algorithmic box that we put a program into and out comes a true/false statement of halting.

Nothing is stopping you from writing the proof manually for each program that you want to prove properties for.

ALSO, you can write sub-turing complete programs. Those are allowed to have automated halting proofs (see idris et al).
1 comments
kevindamm 929 days ago
What you're talking about is actually the Church-Turing thesis and the halting problem.

While, yes, computability and provability are very closely related, it's important to get attribution correct.

More details on what Gödel's Incompleteness Theorem really said are in a sibling comment so I won't repeat them here.

link
Verdex 929 days ago
> it's important to get attribution correct.

Really? Says who?

Or perhaps you'll prove it from first principles. Although if turns out to be difficult, that's okay. Somebody mentioned something about systems being either complete or consistent but never both. Some things can be true but not proveably so. Can't quite remember who it was though.

link
kevindamm 929 days ago
Fair enough, I was being annoyingly pedantic.

[I believe that] it's important to get attribution correct.

link
Verdex 929 days ago
To be fair, annoyingly pedantic is the best kind of pedantic.

- Futurama (kind of)

link
kevindamm 929 days ago
sounds technically correct

Gödel's really was a rather unique mind, and the story of his death is kind of sad.. but I wonder if it takes such a severe kind of paranoia to look for how math can break itself, especially during that time when all the greatest mathematicians were in pursuit of formalizing a complete and consistent mathematics.

link