5 ms·

Well, in math some things are true but not provable unless our formal system is inconsistent. This is one of Gödel's incompleteness theorems. It's therefore no

Well, in math some things are true but not provable unless our formal system is inconsistent. This is one of Gödel's incompleteness theorems. It's therefore not far fetched that some algorithms might in fact always work correctly, but at the same time a proof for their correctness doesn't exist. You can never be sure (literally!) that you're not just confusing it with an algorithm that's wrong but happens to work on all problem instances you've thrown at it so far. IIUC, when the article says unprovable, what it actually means is unproven. To correctly describe an algorithm as unprovable, you would have to have a proof of its unprovability, which would be quite something.

thaumasiotes 12y ago
There's no obstacle in principle to proving that something can't be proved. As far as I understand things, the continuum hypothesis has been shown to be unprovable within ZFC (since ZFC is consistent with both the truth and the falsity of the continuum hypothesis, obviously it is unable to prove the hypothesis true or false), and theoretical computer science produces results of the form "to prove X, the following kinds of approaches cannot work".
- JadeNB 12y ago
  "ZFC is consistent with …" must, of course, be replaced by "If ZFC is consistent, then so are …". In fact, singling out ZFC gives you another example of this kind of result: if ZF is consistent, then so are ZF+C and ZF-C.
  - thaumasiotes 12y ago
    That all depends whether you're comfortable saying a contradiction is "consistent" with an unrelated proposition; I don't see much of a problem with it. Contradictions, being impossible, are logically consistent with everything else. I guess unprovable propositions would switch over to being provable, though.
    - JadeNB 12y ago
      > That all depends whether you're comfortable saying a contradiction is "consistent" with an unrelated proposition; I don't see much of a problem with it. Contradictions, being impossible, are logically consistent with everything else. I guess unprovable propositions would switch over to being provable, though. Oh, I see. I read "A is consistent with B" as "A+B is consistent", but I can see the validity of the reading "A+B is 'as consistent as' A".
dvt 12y ago
What he means when he says "unprovable" is "not provably guaranteed to run in O(x)" since the entire discussion is about complexity. A "provable" algorithm, then, is one where the running time can be calculated. In a deterministic algorithm, this bound will always exist. In a non-deterministic algorithm (e.g. one that uses a random walk), this bound will not. The funny thing is that in the real world (and for big data) the latter algorithms generally run faster than the former. If you're wondering why a non-deterministic algorithm can't have bounds, it's simple! Because it would range from a trivial best case of I get really lucky and randomly hit every "good" factor in constant time O(1) to the trivial worst cast of I get really unlucky and keep guessing the wrong numbers ad infinitum.

thaumasiotes 12y ago

There's no obstacle in principle to proving that something can't be proved. As far as I understand things, the continuum hypothesis has been shown to be unprovable within ZFC (since ZFC is consistent with both the truth and the falsity of the continuum hypothesis, obviously it is unable to prove the hypothesis true or false), and theoretical computer science produces results of the form "to prove X, the following kinds of approaches cannot work".

JadeNB 12y ago
"ZFC is consistent with …" must, of course, be replaced by "If ZFC is consistent, then so are …". In fact, singling out ZFC gives you another example of this kind of result: if ZF is consistent, then so are ZF+C and ZF-C.
- thaumasiotes 12y ago
  That all depends whether you're comfortable saying a contradiction is "consistent" with an unrelated proposition; I don't see much of a problem with it. Contradictions, being impossible, are logically consistent with everything else. I guess unprovable propositions would switch over to being provable, though.
  - JadeNB 12y ago
    > That all depends whether you're comfortable saying a contradiction is "consistent" with an unrelated proposition; I don't see much of a problem with it. Contradictions, being impossible, are logically consistent with everything else. I guess unprovable propositions would switch over to being provable, though. Oh, I see. I read "A is consistent with B" as "A+B is consistent", but I can see the validity of the reading "A+B is 'as consistent as' A".

dvt 12y ago

What he means when he says "unprovable" is "not provably guaranteed to run in O(x)" since the entire discussion is about complexity. A "provable" algorithm, then, is one where the running time can be calculated. In a deterministic algorithm, this bound will always exist. In a non-deterministic algorithm (e.g. one that uses a random walk), this bound will not. The funny thing is that in the real world (and for big data) the latter algorithms generally run faster than the former. If you're wondering why a non-deterministic algorithm can't have bounds, it's simple! Because it would range from a trivial best case of I get really lucky and randomly hit every "good" factor in constant time O(1) to the trivial worst cast of I get really unlucky and keep guessing the wrong numbers ad infinitum.