Z. M. Davis: All this talk of “simpler computer program” seems pretty meaningless to me. A regex matcher in C is long and complex, but in PHP all you have to do is use the built-in preg_match function. (Does the language the universe was written in have a built-in copenhagen_interpretation function?)
One might claim that PHP is a more complicated language than C, but how is that measured? The only way to see how complicated a language is is by a complete description of it—an implementation. And the complexity of an implementation depends on the kind of CPU it must run on, and the complexity of a CPU architecture depends on the laws of physics it must exist in. Self reference: this is the stuff paradoxes are made of.
I’d interpret “shortest computer program” more like ” the shortest string of ones and zeroes that gets the job done on an idealistic Turing machine” or some such. High-level programming languages are for the convenience of programmers, not computers. Thus, to use the built-in preg_match function of PHP, you’d first of all need to represent PHP’s built-in implementation of that, and also the rest of PHP, plus some environment. If you did that I think it would turn out to be longer than if you did the same in C.
This is only to be used as a way of guiding your thoughts in the right direction, a rule of thumb, rather than an actual experiment to determine between hypothesis. Among other problems, how do you know when you have found the shortest possible way of expressing something in ones and zeroes?
The only way to see how complicated a language is is by a complete description of it—an implementation. And the complexity of an implementation depends on the kind of CPU it must run on, and the complexity of a CPU architecture depends on the laws of physics it must exist in.
Z. M. Davis: All this talk of “simpler computer program” seems pretty meaningless to me. A regex matcher in C is long and complex, but in PHP all you have to do is use the built-in preg_match function. (Does the language the universe was written in have a built-in copenhagen_interpretation function?)
One might claim that PHP is a more complicated language than C, but how is that measured? The only way to see how complicated a language is is by a complete description of it—an implementation. And the complexity of an implementation depends on the kind of CPU it must run on, and the complexity of a CPU architecture depends on the laws of physics it must exist in. Self reference: this is the stuff paradoxes are made of.
I’d interpret “shortest computer program” more like ” the shortest string of ones and zeroes that gets the job done on an idealistic Turing machine” or some such. High-level programming languages are for the convenience of programmers, not computers. Thus, to use the built-in preg_match function of PHP, you’d first of all need to represent PHP’s built-in implementation of that, and also the rest of PHP, plus some environment. If you did that I think it would turn out to be longer than if you did the same in C.
This is only to be used as a way of guiding your thoughts in the right direction, a rule of thumb, rather than an actual experiment to determine between hypothesis. Among other problems, how do you know when you have found the shortest possible way of expressing something in ones and zeroes?
You don’t. That’s uncomputable in the general case, and in most nontrivial special cases as well. You can, however, put upper bounds on it.
That was my point exactly.
Fortunately, C and PHP target the same computers.