Dojan comments on Do Scientists Already Know This Stuff? - Less Wrong

21 Post author: Eliezer_Yudkowsky 17 May 2008 02:25AM

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

Comments (51)

Sort By: Old

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

Comment author: Dojan 16 December 2011 03:59:28AM 1 point [-]

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?

Comment author: Nornagest 16 December 2011 04:34:54AM 4 points [-]

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.

Comment author: Dojan 17 December 2011 03:57:11AM 1 point [-]

That was my point exactly.