3 ms·
This is always fascinating to me, that there continues to be interesting structure among computational problems even after you pass the point where they aren't
by cvoss 3y ago
This is always fascinating to me, that there continues to be interesting structure among computational problems even after you pass the point where they aren't computable anymore.
Kind of tangentially, but similar in spirit, I've often wondered about the following: You know how if you can prove False from a system of axioms, then the whole system collapses because you can prove anything from False? Well, surely not all such inconsistent systems are created equal. Right? There's a smallest/first proof of False in each inconsistent system. In some systems it may be very easy to prove False succinctly, while in others it may be a herculean effort to get your first proof of False. So, in that sense, some inconsistent systems are "more consistent" than others, or perhaps "consistent w.r.t particular inconsistencies". I wonder what this "structure among inconsistent systems" looks like!
- chubot 3y agoYeah that is interesting. Maybe one way to paraphrase it is that "infinity" is very big and you can fit a lot of interesting structure there :) It actually turns out that there are infinitely many other problems that are not Turing reducible to any of these ordinary halting problems and to which none of the halting problems are reducible.18 And all these problems have halting problems of their own, defined by the halting of computers that have access to their solutions, that are strictly harder. Similarly with the classic essay Who Can Name the Bigger Number? https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html If you have infinite space, then you can be infinitely clever ... Who can name the bigger number? Whoever has the deeper paradigm.
- ithinkso 3y agoI'm not sure I understand you correctly but in boolean logic it is super hard to be somewhere between truth and false. Fuzzy logic is what you're after
- cvoss 3y agoNo, fuzzy logic is not what I'm after. Nor even the truth or falsity of single statements. I'm interested in the degree to which an entire inconsistent system of logic is inconsistent.
- kmill 3y agoHere's an equivalent-ish problem: Given a programming language, what's the smallest program that's an infinite loop? Some languages are designed to never let you write infinite loops (every program halts in them), but maybe there's a mistake and they accidentally let some non-halting programs slip through.
- nl 3y agoSteven Wolfram talks about related concepts a lot in the frame of his "computational irreducibility" concept. It's interesting to think that there could be systems composed of comparatively simple rules but computing that first proof of False could take longer than the universe. It's interesting, and Wolfram explains it well. You do need to ignore the ego though.