This thread is for the discussion of Less Wrong topics that have not appeared in recent posts. Feel free to rid yourself of cached thoughts by doing so in Old Church Slavonic. If a discussion gets unwieldy, celebrate by turning it into a top-level post.
If you're new to Less Wrong, check out this welcome post.
The complexity doesn't count the amount of data storage required, only the length of the executable code.
looks simple to me.
Yes, but how are you going to represent 'n' under the hood? You are going to need eventually infinite bits to represent it? I guess this is what you mean by storage. I should confess that I don't know enough about alogrithmic information theory so I may be in deeper waters than I can swim. I think you are right though...
I had something more in mind like, the number of bits required to represent any natural number, which is obviously log(n) (or maybe 2loglog(n) - with some clever tricks I think) and if n can get as big as possible, then the complexity, log... (read more)