logoalt Hacker News

cobbaltoday at 4:34 PM1 replyview on HN

I think that's selling the theorems a little short. A math system with arithmetic is equal to, or more powerful than, a computer. For an example, even classical logic comes with the law of excluded middle that can say (internally) if a program halts or not. Incompleteness applies to all the stronger systems as well.


Replies

voxltoday at 6:27 PM

There is no logic that is more expressive than a Turing machine. In fact, just about every logic you know can only expressive necessarily terminating programs. There is a bit of an issue on what exactly someone means by expressive, but if we're talking programs that compute outputs from inputs (without caring about the invariants imposed on said programs) then this holds.