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

2 points by zeynel1 15y ago ↗ HN

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

[ 3.6 ms ] story [ 16.4 ms ] thread

zeynel1 15y ago ↗

http://plus.maths.org/issue37/features/omega/index.html

pseudonym 15y ago ↗

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.

richmassena23 15y ago ↗

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.