There are 2¹⁰²⁴ things you can do with a kilobit(twitter.com)
twitter.com
There are 2¹⁰²⁴ things you can do with a kilobit
https://twitter.com/johncarlosbaez/status/1545818823340613633
79 comments
Most those states are garbage though.
Not at all, you might find any of those states in an encrypted stream.
[deleted]
Unfortunately, we have yet to represent code and data in perfect unison in the perfect format.
I think the term for this is kolmogorov complexity.
My 2012 IOCCC entry https://www.ioccc.org/2012/tromp/hint.html
shows how much you can do with a few dozen bits using a binary form of lambda calculus.
Exactly - the twitter thread would be really improved if everyone read an introduction to information theory. There are 1024 bits of information in a kilobit, and that's enough information for 2^1024 unique messages. The interpreter of the messages judges what the message information means, but the Kolmogorov complexity of a message is inescapable - you would need to modify the interpreter to squeeze out more messages (which is nothing more than pre-transferring information to the receiver)
Shannon’s insight into the hyperspheres of transmission blew my mind 15 years ago, and I’m still not over it.
The idea of an ideal communication channel rivals most ideas ever had. The original paper is surprisingly accessible. Highly recommended if anyone hasn’t had a chance to give it a tour.
And here’s the book, just to not be a tease: https://pure.mpg.de/rest/items/item_2383164/component/file_2...
The idea of an ideal communication channel rivals most ideas ever had. The original paper is surprisingly accessible. Highly recommended if anyone hasn’t had a chance to give it a tour.
And here’s the book, just to not be a tease: https://pure.mpg.de/rest/items/item_2383164/component/file_2...
This is a fantastic paper. Any tips on how to digest some of the more math-y parts of the paper? For example in understanding Theorem 1.
I guess I did take for granted that it includes a bit of calculus and discrete math. I have a little tip.
Once you refresh your knowledge of the greek alphabet, it’s not that scary. Math just needs a lot of symbols.
A good starting point would be infinite series, as this is the basis on which we imagine things bigger than a human lifetime. And it reminds us why we had to define a “limit” as a summation that strangely looks like ∑
It took me years to see the significance of arithmetic series, but as with any ∑, you have to start somewhere! (Often at -∞ and +∞)
The trick to all of it is that there are patterns declared by the underlying structures. There is not really a way to understand them without playing around with equalities and diagrams until you reach a certain zenlike moksha. Trust me, it is quite fulfilling!
Once you refresh your knowledge of the greek alphabet, it’s not that scary. Math just needs a lot of symbols.
A good starting point would be infinite series, as this is the basis on which we imagine things bigger than a human lifetime. And it reminds us why we had to define a “limit” as a summation that strangely looks like ∑
It took me years to see the significance of arithmetic series, but as with any ∑, you have to start somewhere! (Often at -∞ and +∞)
The trick to all of it is that there are patterns declared by the underlying structures. There is not really a way to understand them without playing around with equalities and diagrams until you reach a certain zenlike moksha. Trust me, it is quite fulfilling!
Sorry to rain on your parade, but Kolmogorov Complexity goes to various code paths. Even representing the jump instructions requires multiple bits to be useful…
I digress. Assume a bit for every “if” statement (branch) that is taken within a function (less those that are deeply nested and don’t affect each other). That’s the Kolomogrov complexity.
I digress. Assume a bit for every “if” statement (branch) that is taken within a function (less those that are deeply nested and don’t affect each other). That’s the Kolomogrov complexity.
So we learn the real answer is 256^1024 according to a limited concept of combinations. Its not so good when a mathematician makes such a rudimentary mistake using high school or secondary school mathematics but that's another conversation.
I'm not even sure you can accurately tell me all the uses for a 1 bit value let alone a kilobyte. The number of uses is independent of the number of combinations. If your answer is two you're way off.
Since when does knowing how many combination of states determine what you can do with something? Just because something has 256 states doesn't mean there are 256 different uses for it. There might be 124 uses for binary 00000000. But you won't know that by calculating 2^8.
There might be only three uses for 10100111. One of them makes the world feel pleasant, another melts your face off and another releases three male rabbits into the same cage. But I doubt there's only three. There's likely millions of potential uses for just that pattern alone. How exactly would you calculate how many? Accurately? I'm unconvinced.
The real issue here is lack of imagination. Placing limits where none need exist as well as failing to see possibilities without considering the vastness already present. 2^8 doesn't even begin to cover the number of uses for a single byte.
Rephrased differently: how many uses for a hammer? Can you know only by analysing its orientation? I doubt it.
Rephrased differently (again): feeding a particular combination into different machines will generate a different result. Can you predict the number of results from a given combination without knowing how many machines could process it? I doubt it. The question itself has too many unknowns in it.
I'm not even sure you can accurately tell me all the uses for a 1 bit value let alone a kilobyte. The number of uses is independent of the number of combinations. If your answer is two you're way off.
Since when does knowing how many combination of states determine what you can do with something? Just because something has 256 states doesn't mean there are 256 different uses for it. There might be 124 uses for binary 00000000. But you won't know that by calculating 2^8.
There might be only three uses for 10100111. One of them makes the world feel pleasant, another melts your face off and another releases three male rabbits into the same cage. But I doubt there's only three. There's likely millions of potential uses for just that pattern alone. How exactly would you calculate how many? Accurately? I'm unconvinced.
The real issue here is lack of imagination. Placing limits where none need exist as well as failing to see possibilities without considering the vastness already present. 2^8 doesn't even begin to cover the number of uses for a single byte.
Rephrased differently: how many uses for a hammer? Can you know only by analysing its orientation? I doubt it.
Rephrased differently (again): feeding a particular combination into different machines will generate a different result. Can you predict the number of results from a given combination without knowing how many machines could process it? I doubt it. The question itself has too many unknowns in it.
imagine if you used your powers for good, instead of over-critiquing errors.
He could be an excellent journalist or critic. But he chose to write a comment on HN instead.
Maybe he does both
I got a solid chuckle from this...
Thank you for saying this so that I didn’t have to use my own kilobit to do it.
You can use any pattern for peano numbers, now there is an uncountably infinite number of uses.
This florid critique really lifted my spirits, though.
As other comments suggest, this is a half-truth.
Yes, if an atom was compressible to a bit, you could represent this many universes. It’s analogous to a perfect compression dictionary.
But that’s the rub: an atom isn’t compressible to a bit, at least in this universe. So you have these massive scales competing against each other. The more you say about the atom, the fewer multiverses you have (on an exponential scale!)
It’s an okay way of expressing how many states a kilobyte can take, but what that state means (is it a universe per state or an arrangement of about 1024 ascii characters?) is what’s important.
(Ninja edit: That would imply you can arrange 1024 ascii characters in that-many-universes ways! That’s also fun!)
Yes, if an atom was compressible to a bit, you could represent this many universes. It’s analogous to a perfect compression dictionary.
But that’s the rub: an atom isn’t compressible to a bit, at least in this universe. So you have these massive scales competing against each other. The more you say about the atom, the fewer multiverses you have (on an exponential scale!)
It’s an okay way of expressing how many states a kilobyte can take, but what that state means (is it a universe per state or an arrangement of about 1024 ascii characters?) is what’s important.
(Ninja edit: That would imply you can arrange 1024 ascii characters in that-many-universes ways! That’s also fun!)
That's not what the twitter comment was talking about. It was saying that there are more states in 1KB than the number of atoms in the universe - or 2^8192 > 10^78.
Which is why I support the unique strings— but as you can also tell from many comments, this is not easy for a lot of very technical folk.
What you’re saying is true— if you replace an abstract state with an atom — but the problem here is people are thinking about individual atoms, and not static arrangements of atoms in a in a universe.
Edit: Or, put another way, you changed the game. Of course there are more states in a kilobyte than the sheer number of atoms. But when you start claiming multiverses… no, it doesn’t work. Which the tweet did, and it confuses things.
What you’re saying is true— if you replace an abstract state with an atom — but the problem here is people are thinking about individual atoms, and not static arrangements of atoms in a in a universe.
Edit: Or, put another way, you changed the game. Of course there are more states in a kilobyte than the sheer number of atoms. But when you start claiming multiverses… no, it doesn’t work. Which the tweet did, and it confuses things.
I didn't change the game. That is literally what the tweet was conveying. It then expanded the first claim by what was also a correct statement that each atom could be replaced with a universe of atoms, and still that would not not exceed the number of states in a Kilobyte of memory.
What many people have done is interpret that to mean that somehow complexity theory is broken or that the tweet author was arguing for multiverses. It appears that not everyone actually read the tweet.
> What you’re saying is true— if you replace an abstract state with an atom
That is not at all what was written in my comment. There is no replacement being mentioned anywhere.
What many people have done is interpret that to mean that somehow complexity theory is broken or that the tweet author was arguing for multiverses. It appears that not everyone actually read the tweet.
> What you’re saying is true— if you replace an abstract state with an atom
That is not at all what was written in my comment. There is no replacement being mentioned anywhere.
> and replaced it with a copy of the observable universe, and then did it again
Sorry, it was totally in the tweet. Literally used the word replaced
Sorry, it was totally in the tweet. Literally used the word replaced
[deleted]
> Yes, if an atom was compressible to a bit, you could represent this many universes.
That would be 2^(2^hundreds). That's not the representation that's interesting here.
The interesting comparison is 2^1024 versus the number of things that exist or ever will exist.
If a piece of information has ever been written down, or will ever be written down, you can point to the exact place and exact time in much less than a thousand bits.
That would be 2^(2^hundreds). That's not the representation that's interesting here.
The interesting comparison is 2^1024 versus the number of things that exist or ever will exist.
If a piece of information has ever been written down, or will ever be written down, you can point to the exact place and exact time in much less than a thousand bits.
> Yes, if an atom was compressible to a bit
Isn't it when an atom is compressible to a kilobyte? If a kilobyte were the data, not the alphabet, it would only contain... 8096 atoms.
Isn't it when an atom is compressible to a kilobyte? If a kilobyte were the data, not the alphabet, it would only contain... 8096 atoms.
Right idea on why it’s wrong, but it’s even worse than that! The kilobyte, say all 0s, represents the state of an entire multiverse.
As my comment below, it’s maybe a couple dozen atoms, in perfect conditions (the conditions are again absurd) so this is some definite jiggery-pokery and let’s focus on what they got right? (Ie, how many states a kilobyte can take)
As my comment below, it’s maybe a couple dozen atoms, in perfect conditions (the conditions are again absurd) so this is some definite jiggery-pokery and let’s focus on what they got right? (Ie, how many states a kilobyte can take)
I don't see how you can store an atom with 1 bit. Under most models the position of an atom takes an infinite amount of bits.
You can’t. It’s absurd. That’s my point.
Even if you had a perfect 3D coordinate system and atoms worked on float64 boundaries, you’d still have 64 bits to represent one atom. So you could fit, at best, 128 atoms. These are the competing scales.
Unless you knew ahead of time the exact state of an entire universe, then the kilobyte would be your key into that value, as it were.
(Ninja edit again: you’d need 3 float64s! So 128/3 atoms in a kilobyte. Not much. Point stands)
Even if you had a perfect 3D coordinate system and atoms worked on float64 boundaries, you’d still have 64 bits to represent one atom. So you could fit, at best, 128 atoms. These are the competing scales.
Unless you knew ahead of time the exact state of an entire universe, then the kilobyte would be your key into that value, as it were.
(Ninja edit again: you’d need 3 float64s! So 128/3 atoms in a kilobyte. Not much. Point stands)
AFAIK under the current quantum model (QFT) specifying a precision finer than the Planck length will not make your predictions more accurate. So you only need a finite number of bits to describe a field over a finite volume using a 3-d matrix for each lattice point's amplitude.
You’re right to go to Planck length to get a number of bits to represent an atom, but here’s another angle:
To best guess, there are about 10^24 stars in the sky. That’s about 2^80.
That means you could simply, on Earth-prime, give an id to all the stars in 2^944 universes. Way way less than the multi-multiverse in question, let alone anything atomic.
To best guess, there are about 10^24 stars in the sky. That’s about 2^80.
That means you could simply, on Earth-prime, give an id to all the stars in 2^944 universes. Way way less than the multi-multiverse in question, let alone anything atomic.
Usually the volume isn't assumed to be finite. Sure there is the observable universe, but I don't think many models prohobit atoms from living outside of it.
There are actually way more, since the context associated with those states is virtually limitless.
For example, let's say my wedding is serving salmon or steak, I decide to allocate a single bit to storing those. Now let's say Caesar's thumb gets tired from deciding who lives or dies, so he decides to use a single bit to light up his verdict.
We've now thought of 2*(2^2) "things you can do" with 2 bits.
Also, just from the title: why 2 ^ 1024 and not 2 ^ 8000?
For example, let's say my wedding is serving salmon or steak, I decide to allocate a single bit to storing those. Now let's say Caesar's thumb gets tired from deciding who lives or dies, so he decides to use a single bit to light up his verdict.
We've now thought of 2*(2^2) "things you can do" with 2 bits.
Also, just from the title: why 2 ^ 1024 and not 2 ^ 8000?
And you'd need magnitudes more to explain the state, which is where we are.
How long would the document be to explain that many state flags, even if we did it in ascii and gzipped it?
How long would the document be to explain that many state flags, even if we did it in ascii and gzipped it?
Furthermore, how many such documents are possible? There aren’t 2^1024 things I can do with a kilobit, there’s an unknown and possibly infinite number of things. I can interpret 1024 zeros as the natural number zero, but it could be any number given a different number scheme, or it could be a black image, or a silent audio stream, or as the index to the first of a large number of stories, or as the initial state of 1024 atoms in a tiny binary simulation, or as a series of silent conversations, or...
They use the size of the alphabet (256^1024 different characters) to argue how much data a single character (1 KiB) contains. A single character still can only encode 8096 atoms.
There are 2^8 things you can do with a byte. But you can't do them all at once with a single byte.
There are 2^8 things you can do with a byte. But you can't do them all at once with a single byte.
Sunday funday? If we’re compressing any arbitrary permutation into a finite set of registers, why go wild with a kilobyte? A single on/off switch already has infinite permutations.
Obligatory mention of the Borges short story "The Library of Babel", in which the narrator inhabits a universe of books containing every combination of letters that can fit within some specific number of pages at a specific font size, thus containing every thing that could possibly be written by anyone.
In order to find an interesting book, the integer that points to its location would have the same amount of bytes of information as the book itself, so finding a good book is just as much work as writing it!
The Library of Babel site uses an invertible PRNG for mapping position and content to allow searching
https://libraryofbabel.info/book.cgi
https://libraryofbabel.info/theory4.html
https://libraryofbabel.info/book.cgi
https://libraryofbabel.info/theory4.html
All you need to do is keep the books in a heap by their interestingness. ;) Then finding the most interesting book is Θ(1). It does take a little bit of work to take it off the heap to see what's next on your reading list, though.
Everyone always mentions "The Library of Babel"; considerably fewer bring up the work that inspired it, "The Universal Library" (Die Universalbibliothek) by Kurd Lasswitz [1], which places its treatment of a library containing every possible book of a given length in a somewhat different context.
[1] https://mithilareview.com/lasswitz_09_17/
[1] https://mithilareview.com/lasswitz_09_17/
Also highly recommend "A Short Stay in Hell," a novelette based on the same Library concept. Helps wrap your head around what it means to be in such a place.
This story is seriously fascinating, such a great expansion of the Library Of Babel concept. It really gives a sense of the scale and also the hopelessness of finding _anything_ within the mess. First recommended to me on the horrorlit subreddit, and while it's certainly not traditional horror there is definitely some existential scariness to be found. Strongly recommended.
Room of monkeys + typewriter + time = Shakespeare.
Fuck, we forgot food.
Fuck, we forgot food.
In his book Programming the Universe[0][1], quantum physicist Seth Lloyd calculates that if you had every atom in the universe computing for the age of the universe to generate strings of text randomly, it would not likely have written even the first line of Hamlet. His solution to how we managed to get the entirety of Hamlet plus the rest of Shakespeare's works given much less resources (i.e. evolution on one small planet culminating in one playwright) is that the monkeys/atoms are not typing text into typewriters but instead typing code into a computers.
[0]Programming the Universe, by Seth Lloyd, a great read about physics and computation: https://www.amazon.com/Programming-Universe-Quantum-Computer...
[1]The book is accessible with free account at archive.org: https://archive.org/details/programmingunive00lloy/page/n13/...
[1]Interview with Lloyd where he also mentions this calculation (search for "hamlet"): https://www.technologyreview.com/2006/07/01/39028/qa-seth-ll...
[0]Programming the Universe, by Seth Lloyd, a great read about physics and computation: https://www.amazon.com/Programming-Universe-Quantum-Computer...
[1]The book is accessible with free account at archive.org: https://archive.org/details/programmingunive00lloy/page/n13/...
[1]Interview with Lloyd where he also mentions this calculation (search for "hamlet"): https://www.technologyreview.com/2006/07/01/39028/qa-seth-ll...
I don't get it. I thought a kilobyte is only 2^13?
A kilobyte is ~2^13 bits, but each bit is a power of 2 in regards to "things you can do."
So it's more like 2^2^13.
Technically a kilobyte is 1000 bytes exactly, so I'm not sure why the title says 2^1024 rather than 2^8000, which is the actual number of states in a kilobyte.
So it's more like 2^2^13.
Technically a kilobyte is 1000 bytes exactly, so I'm not sure why the title says 2^1024 rather than 2^8000, which is the actual number of states in a kilobyte.
Lol, I was wondering how long I'd have to scroll to find an accurate definition of kilobyte.
A byte is 8 bits long (2^3), so there are 256 distinct values you can store in a byte (2^(2^3) = 2^8 = 256).
A kilobyte is 8192 bits long (2^13), so there are 2^8192 distinct values you can store in a kilobyte.
A kilobyte is 8192 bits long (2^13), so there are 2^8192 distinct values you can store in a kilobyte.
With 98% accuracy, a Hyperloglog can count ~4Bn distinct 64-bit integers in ~1.5Kb.
Without a data structure, this would take GigaBytes (1M times the space).
That's pretty incredible to me.
Do the combinatorics of every possible combination of 4B distinct 64-bit integers that that 1.5kb can represent.
Mind blowing.
Without a data structure, this would take GigaBytes (1M times the space).
That's pretty incredible to me.
Do the combinatorics of every possible combination of 4B distinct 64-bit integers that that 1.5kb can represent.
Mind blowing.
If I did the calculations correctly, that's over 20 Exabytes worth of data that ~1.5kb could represent with ~98% accuracy.
20 Exabytes is probably close to all the information stored in Google...
20 Exabytes is probably close to all the information stored in Google...
I think what really fastinates me is how much better we can solve a problem if we allows some approximation/uncertainty.
That's 8192 bits, with which you can represent numbers moderately higher than 2^13.
[deleted]
[deleted]
[deleted]
Yeah but do we have any estimates of how much of that 2^1024 things is actually useful / interesting? It feels the number of meaningful programs (not sure how that can be quantified, and even if it is quantified, not sure it can be evaluated given incomputability / incompleteness issues) scales as a polynomial rather than exponential of code size.
Should be 2^8192
Working on things like the busy beaver problem helps us understand how "fancy" you can make a program of a given size.
For 1024 bytes, even with an inefficient instruction encoding, the answer is "pretty fancy".
After all, you can fit a LISP into 512 bytes of x86 code-- https://github.com/jart/sectorlisp . About 64 bytes of that is strings!
In addition to all those programs-- about anything you can write in any language on a page or so fits compressed. So every short poem, etc, small essay, newspaper column, etc.
Working on things like the busy beaver problem helps us understand how "fancy" you can make a program of a given size.
For 1024 bytes, even with an inefficient instruction encoding, the answer is "pretty fancy".
After all, you can fit a LISP into 512 bytes of x86 code-- https://github.com/jart/sectorlisp . About 64 bytes of that is strings!
In addition to all those programs-- about anything you can write in any language on a page or so fits compressed. So every short poem, etc, small essay, newspaper column, etc.
Wikipedia (https://en.wikipedia.org/wiki/Observable_universe#Matter_con...) thinks there are 10^80 atoms in the observable universe, which is approximately 2^240. If you only need to assign a unique ID to each atom, then you need a counter with approximately 240 bits.
But if you needed to store even one bit of information per atom (e.g. whether it is hydrogen or not), then don't you need 2^240 bits uncompressed?
But if you needed to store even one bit of information per atom (e.g. whether it is hydrogen or not), then don't you need 2^240 bits uncompressed?
Yup, his tweets sometime make him seem like the deGrasse Tyson of math, tbh.
(And yes, I am familiar with who John Baez is and his work).
(And yes, I am familiar with who John Baez is and his work).
Not only that but you can then multiply that with all the people you can send it to. Or all the ways you can represent it.
So many bits, so little time.
The smallest chess engine is 488 bytes.
It’s actually down to 288 bytes!
https://leanchess.github.io/#editions
This really blows my mind, as this comment (including the link) is already up to 124 bytes. I’ll include some extra text so that this comment is 288 bytes, just for a clear visual of how little space that actually is :)
https://leanchess.github.io/#editions
This really blows my mind, as this comment (including the link) is already up to 124 bytes. I’ll include some extra text so that this comment is 288 bytes, just for a clear visual of how little space that actually is :)
I wrote a chess program in one bit. Only took a few seconds to write. The interpreter, on the other hand...
Just apply the same process to the interpreter. Easy.
[deleted]
[deleted]
1 KiB or a kilobyte has 256^1024 different states, not 2^1024. Can be written also as 2^(1024 * 8).
This fact is also mentioned in author's own reply, just submitting this comment to avoid other people scratching their heads.