3 ms·
perhaps i am talking out of my ass here, but structured like this, it feels like there is a violation of gödel’s incompleteness theorem somewhere..?
by foxhill 7y ago
perhaps i am talking out of my ass here, but structured like this, it feels like there is a violation of gödel’s incompleteness theorem somewhere..?
- AstralStorm 7y agoNo, the key point is that these systems are still polynomial. You cannot ask a question that would require a non-polynomial computation to provide an answer and expect it to be answered correctly. Most importantly, recursive enumerable already means semidecidable. (Because it consists of primitive recursive functions, which are bounded.) Which means by Godel's theorems it is stronger than Peano arithmetics. (See Tennenbaum's theorem, Presburger arithmetics is fine.)