And then beyond these decidable problems, there is a whole hierarchy of harder and harder undecidable problems, which I think is really cool as well.
https://marienraat.nl/blog/posts/hardest-computational-probl...
https://marienraat.nl/blog/posts/hardest-computational-probl...
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!
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
If you have infinite space, then you can be infinitely clever ...
Who can name the bigger number? Whoever has the deeper paradigm.
It's interesting, and Wolfram explains it well. You do need to ignore the ego though.
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.
http://www.vetta.org/documents/legg-hutter-2006-formal-measu...
In analysis/topology you have this concept of a compact set. Compact sets are "small" - they are close (in a sense) to finite sets, and close (in another sense) to finite-dimensional sets, balls in infinite-dimensional Banach spaces are never compact, etc. (The notion of compactness is one of the most fundamental concept in mathematical analysis.) One of the famous fixed point theorems, Schauder fixed point theorem, asserts that a continuous mapping of a non-empty, compact and convex set has a fixed point. (This is a direct generalization of the Brouwer fixed point theorem, perhaps one of the two most well-known results of this type.)
Now, in 1930 Kuratowski introduced a so-called "measure of non-compactness" - a number saying "how far the given set is from being compact". (Since then, many similar notions were also examined.) There is a very cool family of fixed-point theorems of the type "Let X be some «nice» set and f:X → X some continuous mapping which transforms sets into «less non-compact» sets; then, it has a fixed point." (At least some of those theorems require the axiom of choice, btw. Also, Kuratowski had no idea about them AFAIK, his motivation to consider his measure was completely different.)
Just wondering if CS people have their way of measuring non-decidability of problems... (Probably yes.)
Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf
Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legac...
What has fascinated me (if I'm not mistaken) when I was learning about computational complexity was that P=NP implies that the polynomial hierarchy (so this infinite classes of problem) collapses to P, so all problems in the polynomial hierarchy are solvable in polynomial time.