cousin_it comments on A note on the description complexity of physical theories - Less Wrong

19 Post author: cousin_it 09 November 2010 04:25PM

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

Article Navigation

Comments (177)

Comments (177)

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

Comment author: cousin_it 09 November 2010 09:14:04PM 2 points [-]

if you have an arbitrary program X from the space of all programs that generate an output Y, there can only be a finite number of programs that generate that output more quickly.

Amusingly, this statement is false. If a program Z is faster than X, then there exist infinitely many versions of Z that also run faster than X: just add some never-executed code under an if(false) branch. I'm not sure whether your overall argument can be salvaged.

Comment author: [deleted] 09 November 2010 10:21:50PM 2 points [-]

You're quite correct, there. I was only including code paths that can ever actually be executed, in the same way I wouldn't count comments as part of the program. This seems to me to be the correct thing to do, and I believe one could come up with some more rigorous reasoning along the lines of my previous comment, but I'm too tired right now to do so. I'll think about this...

Comment author: DSimon 10 November 2010 07:00:32PM 3 points [-]

I was only including code paths that can ever actually be executed...

Wouldn't a meta-algorithm that determines which paths are executable in a given algorithm necessarily not be able to do so for every possible algorithm unless it was functionally equivalent to a halting oracle?

I'm not sure how problematic this is to your idea, but it's one advantage that the simpler system of just counting total lines has.

Powered by Reddit Powered by Reddit