tag:blogger.com,1999:blog-9633767.post4315842010843043528..comments2019-02-16T16:07:03.521-08:00Comments on The Curious Wavefunction: Open BordersWavefunctionhttp://www.blogger.com/profile/14993805391653267639noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-9633767.post-75108268831874195012019-01-22T03:30:15.684-08:002019-01-22T03:30:15.684-08:00It's still a quite interesting result and I do...It's still a quite interesting result and I don't mean to degrade it in any way but it just doesn't have the kind of epistemic impact in relation to practical applications of machine learning everyone (and your post) seems to be assuming.Peter Gerdeshttps://www.blogger.com/profile/00124043164362758796noreply@blogger.comtag:blogger.com,1999:blog-9633767.post-60117055188522796522019-01-22T03:28:05.878-08:002019-01-22T03:28:05.878-08:00You are overstating the importance of this result ...You are overstating the importance of this result imo. I mean it was always trivial that we could define some kind of learning style problem the existence of a solution for which is undecidable.<br /><br />Trivial example is this. Say that a computable algorithm learns a function from f: N-> N just if it eventually (finite mistakes) can predict the value of f(n) for all $n$. We know there is an algorithm that succeeds for all primitive recursive functions. What about the function f(n) = 1 if n is less than the length of least proof of contradiction from ZFC and if n is greater than the length of the least proof of contradiction it equals 1 if the n-th Turing machine halts on input n and 0 otherwise. This is trivially learnable iff CON(ZFC) (since if ~CON(ZFC) the function is uncomputable) which by Godel's second theorem is unprovable in ZFC.<br /><br />This isn't what the proof in the paper did by any means and I think it's interesting that they came up with a relatively natural example. However, there is also a way in which one can import elements that are in some sense intuitively outside the domain of machine learning in defining success in a learning algorithm.<br /><br />In particular, the very fact that this depends on the continuum hypothesis tells us that the statement which can't be proved can't even be formulated in second order arithmetic. As such I wouldn't call the undecidability intrinsic to the subject of machine learning (e.g. it, in some sense like the trivial example I gave above, isn't about the kind of statements one intuitively regards as asking questions about machine learnability).Peter Gerdeshttps://www.blogger.com/profile/00124043164362758796noreply@blogger.com