4 ms·

Hilbert's 24th problem

29 points by infinity0 12y ago

heydenberk 12y ago
Seems like this presages this idea of Kolmogorov[0] Complexity by half a century. [0] http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity
- JadeNB 12y ago
  I don't know—there's a big gap between asking "how do you measure this philosophical-sounding quantity?" and actually coming up with a concrete means of doing so. I could ask here "how do you define consciousness for machines?", but (even if I were the first to do so) it wouldn't be fair to say that I'd anticipated Sharmach's landmark 2098 paper solving the problem.
  - infinity0 12y ago
    That might not have been parent's point. I see it more as "this is such a natural thing to want" that mathematicians had been thinking about it, even before we could come up with a coherent definition for the concept. In some ways, this is a good example to avoid making the "fallacy fallacy" - just because someone's argument/reasoning is wrong or incoherent, it doesn't mean the point itself is wrong. https://en.wikipedia.org/wiki/Fallacy_fallacy https://en.wikipedia.org/wiki/Fallacy_fallacy The solution of other similar things like the halting problem, is also a testament to the power of mathematics and formal language, and gives us some hope that this problem (and similar things like consciousness) will be solved in the future.
  - tom_scrace 12y ago
    Sharmach! Pah! Everybody knows that it was Wang-Kleetch who solved the problem in 2094. The charlatan Sharmach merely read the pre-publication draft and claimed the work as his own. It is hard to believe that this nonsense is still being promoted all this time later.
  - hiker 12y ago
    I think Kolmogorov complexity is spot on comparison, considering programs as proofs, theorems as types in the Curry–Howard isomorphism.
- tel 12y ago
  It certainly seems to be asking for proof-relevant mathematics which is funny since my understanding was that Hilbert and Brouwer hated one another http://en.m.wikipedia.org/wiki/Brouwer–Hilbert_controversy http://en.m.wikipedia.org/wiki/Brouwer–Hilbert_controversy
simias 12y ago
I don't understand why there's a "See also" link to the "23 enigma" which as far as I can tell is not related at all to this 24th problem. I'm also not sure it's really worthwhile to post a stub of a wikipedia article on HN without any commentary or context... What is the relevance of this 24th problem? Why is it interesting?
blablabla123 12y ago
While doing my first Analysis for Mathematics course, I had big problems coming up with proofs when I started. So I looked for Books on the topic, didn't really find much (=nothing useful). Seems to be a quite untouched topic...
- jerf 12y ago
  It's one of those things that's really hard to learn without interacting with another human that already knows it. The root problem is the slow batch-process nature of conventional schooling, where you hear something one day, do the homework the next, turn it in the next, and five days later get it back graded, meanwhile having been expected to do another assignment or two. It's a miracle anyone ever learns it under those conditions.
- tel 12y ago
  Typically they're taught in some kind of basic intro course. I did a Graph Theory course basically designed to teach proof techniques. Combinatorics is a good setting for this because it really relies on induction.
- why-el 12y ago
  Books that build on foundational axioms and go on to prove or derive theses/theorems out of them are helpful in your case, since they show you proof construction in action. Pick a classic, something that everyone is familiar with but at the time of its writing it was revolutionary. Euclid's The Elements come to mind.
  - yogabzzz 12y ago
    I can't recommend Euclid's "Elements" with enough emphasis. It really is an amazing book. It gives you a set of ~20 definitions, 10 axioms and then goes on for hundreds of pages constructing proofs using those axioms and the theorems derived from them. All the bullshit and fluff I've seen in standard geometry textbooks is missing... for the reader's benefit.
- jackmaney 12y ago
  Most universities have a course specifically geared towards proofs, including first order propositional and predicate logic, set theory, basic proof techniques, etc. I've taught this particular course a few times when I was in academia, and one of the better books that was around at the time (2004--8) was Krantz's _Elements of Advanced Mathematics_.
Grue3 12y ago
Suppose it is possible to test whether a statement is an axiom in our theory (this is true for finite sets of axioms, or computable infinite sets, i.e. pretty much all sets of axioms used in reality). Suppose there is a finite number of derivation rules (probably will work for computable set of derivation rules). Then it is possible to check whether a statement is derived from axioms in one step, i.e. the set of such statements is computable. By the same reasoning, the set of statements that are derivable in two steps is also computable. And so on. Thus the problem of whether the statement is derivable in less than M steps (if M steps is the shortest known proof) is decidable.

29 points by infinity0 12y ago

Seems like this presages this idea of Kolmogorov[0] Complexity by half a century. [0] http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity

JadeNB 12y ago
I don't know—there's a big gap between asking "how do you measure this philosophical-sounding quantity?" and actually coming up with a concrete means of doing so. I could ask here "how do you define consciousness for machines?", but (even if I were the first to do so) it wouldn't be fair to say that I'd anticipated Sharmach's landmark 2098 paper solving the problem.
- infinity0 12y ago
  That might not have been parent's point. I see it more as "this is such a natural thing to want" that mathematicians had been thinking about it, even before we could come up with a coherent definition for the concept. In some ways, this is a good example to avoid making the "fallacy fallacy" - just because someone's argument/reasoning is wrong or incoherent, it doesn't mean the point itself is wrong. https://en.wikipedia.org/wiki/Fallacy_fallacy https://en.wikipedia.org/wiki/Fallacy_fallacy The solution of other similar things like the halting problem, is also a testament to the power of mathematics and formal language, and gives us some hope that this problem (and similar things like consciousness) will be solved in the future.
- tom_scrace 12y ago
  Sharmach! Pah! Everybody knows that it was Wang-Kleetch who solved the problem in 2094. The charlatan Sharmach merely read the pre-publication draft and claimed the work as his own. It is hard to believe that this nonsense is still being promoted all this time later.
- hiker 12y ago
  I think Kolmogorov complexity is spot on comparison, considering programs as proofs, theorems as types in the Curry–Howard isomorphism.
tel 12y ago
It certainly seems to be asking for proof-relevant mathematics which is funny since my understanding was that Hilbert and Brouwer hated one another http://en.m.wikipedia.org/wiki/Brouwer–Hilbert_controversy http://en.m.wikipedia.org/wiki/Brouwer–Hilbert_controversy

simias 12y ago

I don't understand why there's a "See also" link to the "23 enigma" which as far as I can tell is not related at all to this 24th problem. I'm also not sure it's really worthwhile to post a stub of a wikipedia article on HN without any commentary or context... What is the relevance of this 24th problem? Why is it interesting?

blablabla123 12y ago

While doing my first Analysis for Mathematics course, I had big problems coming up with proofs when I started. So I looked for Books on the topic, didn't really find much (=nothing useful). Seems to be a quite untouched topic...

jerf 12y ago
It's one of those things that's really hard to learn without interacting with another human that already knows it. The root problem is the slow batch-process nature of conventional schooling, where you hear something one day, do the homework the next, turn it in the next, and five days later get it back graded, meanwhile having been expected to do another assignment or two. It's a miracle anyone ever learns it under those conditions.
tel 12y ago
Typically they're taught in some kind of basic intro course. I did a Graph Theory course basically designed to teach proof techniques. Combinatorics is a good setting for this because it really relies on induction.
why-el 12y ago
Books that build on foundational axioms and go on to prove or derive theses/theorems out of them are helpful in your case, since they show you proof construction in action. Pick a classic, something that everyone is familiar with but at the time of its writing it was revolutionary. Euclid's The Elements come to mind.
- yogabzzz 12y ago
  I can't recommend Euclid's "Elements" with enough emphasis. It really is an amazing book. It gives you a set of ~20 definitions, 10 axioms and then goes on for hundreds of pages constructing proofs using those axioms and the theorems derived from them. All the bullshit and fluff I've seen in standard geometry textbooks is missing... for the reader's benefit.
jackmaney 12y ago
Most universities have a course specifically geared towards proofs, including first order propositional and predicate logic, set theory, basic proof techniques, etc. I've taught this particular course a few times when I was in academia, and one of the better books that was around at the time (2004--8) was Krantz's _Elements of Advanced Mathematics_.

Grue3 12y ago

Suppose it is possible to test whether a statement is an axiom in our theory (this is true for finite sets of axioms, or computable infinite sets, i.e. pretty much all sets of axioms used in reality). Suppose there is a finite number of derivation rules (probably will work for computable set of derivation rules). Then it is possible to check whether a statement is derived from axioms in one step, i.e. the set of such statements is computable. By the same reasoning, the set of statements that are derivable in two steps is also computable. And so on. Thus the problem of whether the statement is derivable in less than M steps (if M steps is the shortest known proof) is decidable.