Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

CuSithBell comments on Occam's Razor - Less Wrong

37 Post author: Eliezer_Yudkowsky 26 September 2007 06:36AM

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

Comments (52)

Sort By: Old

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

Comment author: CuSithBell 20 March 2011 05:59:28PM 1 point [-]

What is the reasoning behind using a prefix-free set?

Comment author: cousin_it 20 March 2011 06:09:23PM *  3 points [-]

Apart from giving a simple formula for the prior, it comes in handy in other theoretical constructions. For example, if you have a "universal Turing machine" (a computer than can execute arbitrary programs) and feed it an infinite input stream of bits, perhaps coming from a random source because you intend to "execute a random program"... then it needs to know where the program ends. You could introduce an end-of-program marker, but a more general solution is to make valid programs form a prefix-free set, so that when the machine has finished reading a valid program, it knows that reading more bits won't result in a longer but still valid program. (Note that adding an end-of-program marker is one of the ways to make your set of programs prefix-free!)

Overall this is a nice example of an idea that "just smells good" to a mathematician's intuition.

Comment author: CuSithBell 20 March 2011 06:21:32PM *  0 points [-]

Ah! I must have had a brain-stnank - this makes total sense in math / theoretical CS terms, I was substituting an incorrect interpretation of "hypothesis" when reading the comment out of context. Thanks :)