endoself comments on Description complexity: an apology and note on terminology - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (13)
The above is not as strong as it seems. It can be shown that on any given Turing machine, the prior probability of an equivalence class of programs is at most an O(1) factor greater than the part of that probability due to just the simplest program in the class.
Arguments can still be suspect if you don't know which program is the simplest. However, it is often possible to show that a program is probably the simplest; since there are many more complex programs than simple ones, a randomly drawn complex hypothesis is extremely unlikely to have a shorter equivalent.