There are 2¹⁰²⁴ things you can do with a kilobit

https://twitter.com/johncarlosbaez/status/1545818823340613633

by Tomte • 4 years ago

68 68 4 years ago

twitter.com

sidcool• 4 years ago

I don't understand. Aren't those possible states?

_fn• 4 years ago

I don't get it. I thought a kilobyte is only 2^13?

bigDinosaur• 4 years ago

That's 8192 bits, with which you can represent numbers moderately higher than 2^13.

mbrubeck• 4 years ago

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.

onlyrealcuzzo2• 4 years ago

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.

ralusek3• 4 years ago

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.

fumeux_fume• 4 years ago

Lol, I was wondering how long I'd have to scroll to find an accurate definition of kilobyte.

polishdude20• 4 years ago

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.

donkarma• 4 years ago

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.

wlib• 4 years ago

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)

b33j0r2• 4 years ago

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...

barakm7• 4 years ago

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.

tromp• 4 years ago

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.

eyelidlessness• 4 years ago

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.

scrame• 4 years ago

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?

dahart• 4 years ago

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...

aerovistae• 4 years ago

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.

ralusek3• 4 years ago

Room of monkeys + typewriter + time = Shakespeare.

Fuck, we forgot food.

uplifter• 4 years ago

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...

porphyra• 4 years ago

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!

mlyle2• 4 years ago

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.

mgdlbp• 4 years ago

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

thrtythreeforty• 4 years ago

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.

agentwiggles• 4 years ago

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.

Arcorann• 4 years ago

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/

ralusek3• 4 years ago

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?

sys_64738• 4 years ago

The smallest chess engine is 488 bytes.

KMnO4• 4 years ago

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 :)

cyclotron3k• 4 years ago

I wrote a chess program in one bit. Only took a few seconds to write. The interpreter, on the other hand...

ummonk• 4 years ago

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.

mlyle2• 4 years ago

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.

marris• 4 years ago

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?

moralestapia• 4 years ago

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).

vardump2• 4 years ago

That's of course not correct.

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.

whateveracct• 4 years ago

Most those states are garbage though.

dTal• 4 years ago

Not at all, you might find any of those states in an encrypted stream.

mejutoco• 4 years ago

The title mentions a kilo_bit_. Maybe it has changed since the posting.

vardump2• 4 years ago

Yes, it was originally "... things you can do with a kilobyte."

layer8• 4 years ago

So many bits, so little time.

barakm7• 4 years ago

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!)

charcircuit2• 4 years ago

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.

ReaLNero• 4 years ago

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.

barakm7• 4 years ago

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)

ketzu2• 4 years ago

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.

barakm7• 4 years ago

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)

IncRnd2• 4 years ago

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.

barakm7• 4 years ago

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.

Dylan16807• 4 years ago

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.

ketzu2• 4 years ago

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.

adamius• 4 years ago

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.

naikrovek2• 4 years ago

imagine if you used your powers for good, instead of over-critiquing errors.

semitones• 4 years ago

I got a solid chuckle from this...

memorable• 4 years ago

He could be an excellent journalist or critic. But he chose to write a comment on HN instead.

zeroth32• 4 years ago

He did use its power for good. It is a good introduction to information theory and encoding.

I was going to write something very similar, now I can use that time better.

satisfice• 4 years ago

Thank you for saying this so that I didn’t have to use my own kilobit to do it.

imtringued• 4 years ago

You can use any pattern for peano numbers, now there is an uncountably infinite number of uses.

Khelavaster• 4 years ago

This florid critique really lifted my spirits, though.

There are 2¹⁰²⁴ things you can do with a kilobit

Related Stories