Yup, Kolmogorov complexity is only concerned with the length of the shortest algorithm. There are other measures (more rarely used, it seems) that take into account things like memory used, or time (number of steps), though I can’t remember their name just now.
Note that usually the complexity of X is the size of the program that outputs X exactly, not the program that outputs a lot of things including X. Otherwise you can write a quite short program that outputs, say, all possible ascii texts, and claim that it’s size is an upper bound of the complexity of the Bible. Actually, the information needed to generate the Bible is the same as the information to locate the Bible in all those texts.
Example in Python:
chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'+\
'"!#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r'
def iter_strings_of_size(n):
if n <= 0:
yield ''
else:
for string in iter_strings_of_size(n-1):
for char in chars:
yield string + char
def iter_all_strings():
n = 0
while True:
for string in iter_strings_of_size(n):
yield string
n = n + 1
Understanding the Power of Yield was a great step forwards for me, afterwards I was horrified to reread some old code that was riddled with horrible classes like DoubleItemIterator and IteratorFilter that my C++-addled brain had cooked up, and realized half my classes were useless and the rest could have there linecount divided by ten.
And some people still cound “lines of code” as a measure of productivity. Sob.
Yup, Kolmogorov complexity is only concerned with the length of the shortest algorithm. There are other measures (more rarely used, it seems) that take into account things like memory used, or time (number of steps), though I can’t remember their name just now.
Note that usually the complexity of X is the size of the program that outputs X exactly, not the program that outputs a lot of things including X. Otherwise you can write a quite short program that outputs, say, all possible ascii texts, and claim that it’s size is an upper bound of the complexity of the Bible. Actually, the information needed to generate the Bible is the same as the information to locate the Bible in all those texts.
Example in Python:
This has improved my understanding of the Python “yield” statement.
Glad I could be of use !
Understanding the Power of Yield was a great step forwards for me, afterwards I was horrified to reread some old code that was riddled with horrible classes like DoubleItemIterator and IteratorFilter that my C++-addled brain had cooked up, and realized half my classes were useless and the rest could have there linecount divided by ten.
And some people still cound “lines of code” as a measure of productivity. Sob.
So that’s why my self-enhancing AI keeps getting bogged down!
Voted up for being really funny.
“Actually, the information needed to generate the Bible is the same as the information to locate the Bible in all those texts.”
Or to locate it in “The Library of Babel”.