4 ms·
I have a more up-to-date list at https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete
by gwern 8y ago
I have a more up-to-date list at https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete
- Y_Y 8y agoI've heard you can perform arbitrarily difficult calculations just by getting gwern interested enough to write an article.
- eindiran 8y agoWhy do you consider it surprising that Peano Arithmetic is Turing complete?
- gwern 8y agoBecause they're supposed to just be the integers. If it is obvious to you that 'the integers' means undecidability/Turing-completeness, and that integers without multiplication (Presburger) does not, then all I can say is that your mathematical logic intuition is vastly superior to mine and everyone before Turing/Godel.