Archive for Kurt Gödel

undecidable learnability

Posted in Books, Statistics, Travel, University life with tags , , , , , , on February 15, 2019 by xi'an

“There is an unknown probability distribution P over some finite subset of the interval [0,1]. We get to see m i.i.d. samples from P for m of our choice. We then need to find a finite subset of [0,1] whose P-measure is at least 2/3. The theorem says that the standard axioms of mathematics cannot be used to prove that we can solve this problem, nor can they be used to prove that we cannot solve this problem.”

In the first issue of the (controversial) nature machine intelligence journal, Ben-David et al. wrote a paper they present a s the machine learning equivalent to Gödel’s incompleteness theorem. The result is somewhat surprising from my layman perspective and it seems to only relate to a formal representation of statistical problems. Formal as in the Vapnik-Chervonenkis (PAC) theory. It sounds like, given a finite learning dataset, there are always features that cannot be learned if the size of the population grows to infinity, but this is hardly exciting…

The above quote actually makes me think of the Robbins-Wasserman counter-example for censored data and Bayesian tail prediction, but I am unsure the connection is anything more than sheer fantasy..!

Randomness through computation

Posted in Books, Statistics, University life with tags , , , , , , , , , , , , , , on June 22, 2011 by xi'an

A few months ago, I received a puzzling advertising for this book, Randomness through Computation, and I eventually ordered it, despite getting a rather negative impression from reading the chapter written by Tomasso Toffoli… The book as a whole is definitely perplexing (even when correcting for this initial bias) and I would not recommend it to readers interested in simulation, in computational statistics or even in the philosophy of randomness. My overall feeling is indeed that, while there are genuinely informative and innovative chapters in this book, some chapters read more like newspeak than scientific material (mixing the Second Law of Thermodynamics, Gödel’s incompleteness theorem, quantum physics, and NP completeness within the same sentence) and do not provide a useful entry on the issue of randomness. Hence, the book is not contributing in a significant manner to my understanding of the notion. (This post also appeared on the Statistics Forum.) Continue reading


Posted in Books with tags , , , , , , on December 11, 2010 by xi'an

Thanks to Judith Rousseau (who gave me the book to read), I have enjoyed very much Logicomix: An epic search for truth, which is written in the format of a comic book or a graphic novel (just like Nietzsche, even though it is drawn in an altogether different if pleasant and colourful style). This bestselling book is about Bertrand Russell‘s doomed quest for the logical foundations of mathematics and about the intense debates in the philosophical and mathematical communities at the turn of the  century, ending with Gödel’s incompleteness theorem and Wittgenstein’s Tractatus Philosophicus. (Which reminded me of another book, Wittgenstein’s poker, that I read ages ago.)

Continue reading

Mathematics and realism

Posted in Books with tags , , , , , , , , , , , on November 27, 2010 by xi'an

I read in Liberation a rather surprising tribune (in French) by “Yann Moix, writer”. The starting point is a criticism of Stephen Hawking (and Leonard Mlodinow)’s recent book The Grand Design, With regards to its conclusion that a god is not necessary to explain the creation and the working of the Universe: “It is not necessary to invoke God to light the blue touch paper and set the universe going.” I haven’t read Hawking’s book (although I briefly considered buying it in London last time I was there, here is a Guardian review), I had never heard before of this (controversial) writer, and I do not see the point in debating about supernatural beings (except when reviewing a fantasy book!). However, the arguments of Moix are rather limited from a philosophical viewpoint.

Continue reading