Well, firstly, who said I cared at all about ‘heresy’? I’m not replying here in order to demonstrate my adherence to the First Church Of Bayes or something...
And while there are, obviously, occasions where ordering by running time and code length are opposed, in general when comparing two arbitrary programs which generate the same output, the longer one will also take longer. This is obvious when you consider it—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. However, there are an infinite number of programs in the sample space that will generate the output more slowly, and that are also longer than X—just keep adding an extra ‘sleep 1’ before it prints the output, to take a trivial example.
In general, the longer the program, the more operations it performs and the longer it takes, when you’re sampling from the space of all possible programs. So while run time and code length aren’t perfectly correlated, they’re a very decent proxy for each other.
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.
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...
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.
Well, firstly, who said I cared at all about ‘heresy’? I’m not replying here in order to demonstrate my adherence to the First Church Of Bayes or something...
And while there are, obviously, occasions where ordering by running time and code length are opposed, in general when comparing two arbitrary programs which generate the same output, the longer one will also take longer. This is obvious when you consider it—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. However, there are an infinite number of programs in the sample space that will generate the output more slowly, and that are also longer than X—just keep adding an extra ‘sleep 1’ before it prints the output, to take a trivial example.
In general, the longer the program, the more operations it performs and the longer it takes, when you’re sampling from the space of all possible programs. So while run time and code length aren’t perfectly correlated, they’re a very decent proxy for each other.
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.
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...
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.