6 ms·

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://m

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-problems/ https://marienraat.nl/blog/posts/hardest-computational-probl...

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 ago
  Yeah 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 ago
  I'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 ago
    No, 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 ago
    Here'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.
    - kevinwang 3y ago
      Seems like it wouldn't be Turing complete if you couldn't make an infinite loop
      - kmill 3y ago
        Yep. Still, it turns out there's a lot you can do with non-Turing-complete languages, and it's nice knowing that a program will definitely finish.
- nl 3y ago
  Steven 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.
JoeDaDude 3y ago
I remember my head exploding upon seeing a presentation on the work of Larry Stockmeyer. Though he was an academic working in the obscure discipline of theoretical computer science, he ended up being named in a science fiction novel. Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf https://lance.fortnow.com/papers/files/beyondnp.pdf Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legacy-of-larry-stockmeyer https://www.slideserve.com/leda/beyond-np-the-work-and-legac...
semihsalihoglu 3y ago
I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wikipedia.org/wiki/Polynomial_hierarchy 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.
- legobmw99 3y ago
  Your understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem
zbobet2012 3y ago
One of the more interesting undecidable problems out there is kolmogorov complexity. It basically asks the question: given a string what is the smallest program that generates that string. Which fundamentally is the question of compression. So these undecidable problems actually have a lot of practical value. https://en.m.wikipedia.org/wiki/Kolmogorov_complexity https://en.m.wikipedia.org/wiki/Kolmogorov_complexity
- nl 3y ago
  And Kolmogorov complexity is used by Shane Legg (DeepMind founder) and Marcus Hutter (Hutter prize etc) in their paper "A Formal Measure of Machine Intelligence" http://www.vetta.org/documents/legg-hutter-2006-formal-measure-intelligence.pdf http://www.vetta.org/documents/legg-hutter-2006-formal-measu...
mbork_pl 3y ago
This is a very loose association from someone coming from mathematical analysis background, maybe interesting for some people. 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.)

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 ago
Yeah 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 ago
I'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 ago
  No, 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 ago
  Here'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.
  - kevinwang 3y ago
    Seems like it wouldn't be Turing complete if you couldn't make an infinite loop
    - kmill 3y ago
      Yep. Still, it turns out there's a lot you can do with non-Turing-complete languages, and it's nice knowing that a program will definitely finish.
nl 3y ago
Steven 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.

JoeDaDude 3y ago

I remember my head exploding upon seeing a presentation on the work of Larry Stockmeyer. Though he was an academic working in the obscure discipline of theoretical computer science, he ended up being named in a science fiction novel. Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf https://lance.fortnow.com/papers/files/beyondnp.pdf Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legacy-of-larry-stockmeyer https://www.slideserve.com/leda/beyond-np-the-work-and-legac...

semihsalihoglu 3y ago

I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wikipedia.org/wiki/Polynomial_hierarchy 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.

legobmw99 3y ago
Your understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem

zbobet2012 3y ago

One of the more interesting undecidable problems out there is kolmogorov complexity. It basically asks the question: given a string what is the smallest program that generates that string. Which fundamentally is the question of compression. So these undecidable problems actually have a lot of practical value. https://en.m.wikipedia.org/wiki/Kolmogorov_complexity https://en.m.wikipedia.org/wiki/Kolmogorov_complexity

nl 3y ago
And Kolmogorov complexity is used by Shane Legg (DeepMind founder) and Marcus Hutter (Hutter prize etc) in their paper "A Formal Measure of Machine Intelligence" http://www.vetta.org/documents/legg-hutter-2006-formal-measure-intelligence.pdf http://www.vetta.org/documents/legg-hutter-2006-formal-measu...

mbork_pl 3y ago

This is a very loose association from someone coming from mathematical analysis background, maybe interesting for some people. 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.)