News for hackers. Stuff that matters.

Ask HN: Size of a program as a measure of simplicity?

In this article http://plus.maths.org/issue37/features/omega/index.html Gregory Chaitin says that "... simplicity — or lack of it — [of scientific law] is reflected in the length of the program."

Since "the size of a computer program is the number of "bits" it contains"; Chaitin measures simplicity with the number of bits in a program.

This doesn't sound right to me. All "hello world" programs achieve the same result; but all "hello world" programs do not have the same number of bits; as far as I know.

Anyone care to comment?

( 3 comments | 2 points | on HN )
Re:Ask HN: Size of a program as a measure of simplicity? by pseudonym on Thursday September 30, 2010 @10:56PM (#1745806)
I'll just leave this here.

http://www.maths.tcd.ie/~nryan/demos/index.html

Anyone who thinks program complexity is judged solely on program size has never written a demo, or participated in a JAPH/Perl Golf competition.

Re:Ask HN: Size of a program as a measure of simplicity? by richmassena23 on Friday October 01, 2010 @12:51AM (#1746058)
I would not say the length of the program, but the number of possible states (which may not be a computable function, someone correct me, is this Kolmogorov complexity?) which determines simplicity.
Re:Ask HN: Size of a program as a measure of simplicity? by zeynel1 on Thursday September 30, 2010 @10:30PM (#1745745)