5 ms·

They already do. Incompleteness Theorem ("some logical statements are true but are unprovable", e.g., "this program will terminate" for some arbitrary programs

by strlen 15y ago

They already do. Incompleteness Theorem ("some logical statements are true but are unprovable", e.g., "this program will terminate" for some arbitrary programs a.k.a. the Halting Problem) is one of the most significant achievements in logic. Here's philosophers' take on Kurt Godel: http://plato.stanford.edu/entries/goedel/ http://plato.stanford.edu/entries/goedel/ I am, however, curious as to how other problems in computational complexity figure in philosophy, e.g., P vs. NP completeness. Wish I had the time to read the essay.

gwern 15y ago
> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic. Aaronson covers this, pointing out that those results are both in computability theory, not complexity.
- strlen 15y ago
  Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines. Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.
  - psykotic 15y ago
    > (much like NP-Complete problems are a subset of Complete problems) That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."
    - Sniffnoy 15y ago
      Or perhaps he meant that NP-complete problems are a subset of NP-hard problems? But that wouldn't be analogous... (Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's intermediate? Is this something that's known?)
      - psykotic 15y ago
        I hate it when a pedantic correction backfires. I should have been more careful. :) You're right to raise that question. It's a classical result of computability theory that there exists an undecidable problem that is strictly easier than the halting problem: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_and_the_priority_method http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_...
        Sniffnoy 15y ago
        Also I just realized that just because something is at least as hard as the halting problem, doesn't necessarily mean it stays so when you restrict to polynomial-time reductions. So maybe even what I stated above isn't true. :-/ Well, the halting problem is NP-hard, at any rate. :P
      - JoshuaZ 15y ago
        Uncomputable problems are not necessarily NP-hard. You can for example encode a version of the halting problem such that the instances are simply very long. For example, consider the language L defined by k is in L iff k=2^2^2^n for some n and nth Turing machine halts on the blank tape (some reasonable listing of Turing machines). In order to feed an NP-hard problem to an L-oracle, one needs to ridiculously expand the length of the problem far more than polynomial length so this certainly can't be done in polynomial time.
        Sniffnoy 15y ago
        Ah, good one. Hooray for padding tricks!
    - vbtemp 15y ago
      How could undecidable problems possibly be a sub-set of NP-Hard problems? All the complexity classes fall within the realm of computable problems.
    - strlen 15y ago
      No, NP-hard problems can still be solved, just not in polynomial time.
  - Sniffnoy 15y ago
    > I always thought of complexity as being a subset of computability theory But while that's certainly true in a sense, that doesn't imply what you stated -- just because they care about computability theory doesn't mean they care about this aspect of it.
snoochybooch 15y ago
Godel's incompleteness theorems do not assert that particular statements cannot be proven. Furthermore, the "Haklting Problem" is not a statement.
jerf 15y ago
I haven't read the paper, but here's one example I've seen. Assume for the moment that the universe is closed, complete (there is nothing but our universe), and deterministic under the hood. Obviously, nobody in the universe has free will, right? Because it's all closed and all outcomes are predetermined. But maybe that's not a useful definition of free will. The conventional, fuzzy definition of free will has an omniscient narrator in it; "I do not have free will if the omniscient narrator knows in advance everything I will do" is a reasonable expansion of the conventional idea. But in my hypothesized universe, there is no omniscient narrator. There are only various entities with various degrees of computational power, with a varying but rather quantifiable amount of information that any entity can obtain about any other. Suppose it can be demonstrated that it is computationally infeasible for any entity due to being too complex to ever predict the actions of any human-sized (or greater) other entity, even if granted all the remaining resources in the universe to compute the actions. Or suppose it is demonstrated to be quite easy. Either way, that would be an interesting philosophical contribution, no? (I'm just sketching the idea here. I'm not trying to defend it or attack it. Oh, and one of the foundations of philosophy is that there is never One True Definition; all loaded terms in this post are ultimately ill-defined, and I've avoided the distraction of even beginning to nail them down on purpose.)
- ionfish 15y ago
  Your suggestion confuses an epistemic limitation with a metaphysical one. Just because no one knows what we're going to do next doesn't mean there isn't a fact of the matter about it. While the idea of God looking down on us from on high is a compelling story, if you take God away but leave determinism it doesn't do anything to resolve the problem: our actions are still pre-determined and cannot be changed. Of course, whether or not that makes us free is a further question. A compatibilist [1] would claim that we are. [1] http://plato.stanford.edu/entries/compatibilism/ http://plato.stanford.edu/entries/compatibilism/
  - yters 15y ago
    Compatibilism is just one of those "answers" that defines away the problem. "Oh, if we just say that free will is determined then problem solved! I'm a genius!" Also, FWIW omniscience is not logically incompatible with free will.
Jach 15y ago
The incompleteness theorem has an interesting "workaround": http://stirling-westrup-tt.blogspot.com/2011/07/tt-ns-2823-ultimate-logic-to-infinity.html http://stirling-westrup-tt.blogspot.com/2011/07/tt-ns-2823-u...
vbtemp 15y ago
No, incompleteness and its generalizations fall within computability theory, not complexity theory. In regard to your second point, you say "other problems in computational complexity". Again, you mentioned computability theory, not CCT. They are different endeavors. Aaronson was careful to say that this is not another essay on philosophy and computability.

by strlen 15y ago

gwern 15y ago

> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic. Aaronson covers this, pointing out that those results are both in computability theory, not complexity.

strlen 15y ago
Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines. Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.
- psykotic 15y ago
  > (much like NP-Complete problems are a subset of Complete problems) That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."
  - Sniffnoy 15y ago
    Or perhaps he meant that NP-complete problems are a subset of NP-hard problems? But that wouldn't be analogous... (Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's intermediate? Is this something that's known?)
    - psykotic 15y ago
      I hate it when a pedantic correction backfires. I should have been more careful. :) You're right to raise that question. It's a classical result of computability theory that there exists an undecidable problem that is strictly easier than the halting problem: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_and_the_priority_method http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_...
      - Sniffnoy 15y ago
        Also I just realized that just because something is at least as hard as the halting problem, doesn't necessarily mean it stays so when you restrict to polynomial-time reductions. So maybe even what I stated above isn't true. :-/ Well, the halting problem is NP-hard, at any rate. :P
    - JoshuaZ 15y ago
      Uncomputable problems are not necessarily NP-hard. You can for example encode a version of the halting problem such that the instances are simply very long. For example, consider the language L defined by k is in L iff k=2^2^2^n for some n and nth Turing machine halts on the blank tape (some reasonable listing of Turing machines). In order to feed an NP-hard problem to an L-oracle, one needs to ridiculously expand the length of the problem far more than polynomial length so this certainly can't be done in polynomial time.
      - Sniffnoy 15y ago
        Ah, good one. Hooray for padding tricks!
  - vbtemp 15y ago
    How could undecidable problems possibly be a sub-set of NP-Hard problems? All the complexity classes fall within the realm of computable problems.
  - strlen 15y ago
    No, NP-hard problems can still be solved, just not in polynomial time.
- Sniffnoy 15y ago
  > I always thought of complexity as being a subset of computability theory But while that's certainly true in a sense, that doesn't imply what you stated -- just because they care about computability theory doesn't mean they care about this aspect of it.

snoochybooch 15y ago

Godel's incompleteness theorems do not assert that particular statements cannot be proven. Furthermore, the "Haklting Problem" is not a statement.

jerf 15y ago

I haven't read the paper, but here's one example I've seen. Assume for the moment that the universe is closed, complete (there is nothing but our universe), and deterministic under the hood. Obviously, nobody in the universe has free will, right? Because it's all closed and all outcomes are predetermined. But maybe that's not a useful definition of free will. The conventional, fuzzy definition of free will has an omniscient narrator in it; "I do not have free will if the omniscient narrator knows in advance everything I will do" is a reasonable expansion of the conventional idea. But in my hypothesized universe, there is no omniscient narrator. There are only various entities with various degrees of computational power, with a varying but rather quantifiable amount of information that any entity can obtain about any other. Suppose it can be demonstrated that it is computationally infeasible for any entity due to being too complex to ever predict the actions of any human-sized (or greater) other entity, even if granted all the remaining resources in the universe to compute the actions. Or suppose it is demonstrated to be quite easy. Either way, that would be an interesting philosophical contribution, no? (I'm just sketching the idea here. I'm not trying to defend it or attack it. Oh, and one of the foundations of philosophy is that there is never One True Definition; all loaded terms in this post are ultimately ill-defined, and I've avoided the distraction of even beginning to nail them down on purpose.)

ionfish 15y ago
Your suggestion confuses an epistemic limitation with a metaphysical one. Just because no one knows what we're going to do next doesn't mean there isn't a fact of the matter about it. While the idea of God looking down on us from on high is a compelling story, if you take God away but leave determinism it doesn't do anything to resolve the problem: our actions are still pre-determined and cannot be changed. Of course, whether or not that makes us free is a further question. A compatibilist [1] would claim that we are. [1] http://plato.stanford.edu/entries/compatibilism/ http://plato.stanford.edu/entries/compatibilism/
- yters 15y ago
  Compatibilism is just one of those "answers" that defines away the problem. "Oh, if we just say that free will is determined then problem solved! I'm a genius!" Also, FWIW omniscience is not logically incompatible with free will.

Jach 15y ago

The incompleteness theorem has an interesting "workaround": http://stirling-westrup-tt.blogspot.com/2011/07/tt-ns-2823-ultimate-logic-to-infinity.html http://stirling-westrup-tt.blogspot.com/2011/07/tt-ns-2823-u...

vbtemp 15y ago

No, incompleteness and its generalizations fall within computability theory, not complexity theory. In regard to your second point, you say "other problems in computational complexity". Again, you mentioned computability theory, not CCT. They are different endeavors. Aaronson was careful to say that this is not another essay on philosophy and computability.