shokwave comments on An Intuitive Explanation of Solomonoff Induction - Less Wrong

53 Post author: Alex_Altair 11 July 2012 08:05AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (210)

You are viewing a single comment's thread. Show more comments above.

Comment author: MyrddinE 11 July 2012 09:21:27PM 1 point [-]

I am a bit confused... how do you reconcile SI with Gödel's incomleteness theorum. Any rigid symbolic system (such as one that defines the world in binary) will invariably have truths that cannot be proven within the system. Am I misunderstanding something?

Comment author: shokwave 11 July 2012 09:41:59PM 4 points [-]

The post covers that, though not by that name:

And even more problematic, some of the algorithms will run forever without producing output—and we can't prove they will never stop running. This is known as the halting problem, and it is a deep fact of the theory of computation.

When Solomonoff induction runs into a halting problem it may well run forever. This is a part of why it's uncomputable. Uncomputable is a pretty good synonym for unprovable, in this case.