15
$\begingroup$

My main character has access to the entire knowledge of humanity (note: This is year 4000s so they have much more than "our humanity"). He created another consciousness for himself; this new consciousness has limited capacity which is way way smaller than the entire humanity's knowledge he has access to, so in the story he compresses this library of knowledge and puts it inside this new consciousness.

For more context, he can't expand his capacity with servers or other data storage methods, the only capacity available is that of his new consciousness.

He also doesn't have access to magic.

The main question is: is it is possible to compress knowledge infinitely? If not, what would the roughly smallest ratio you could compress information be?

He can use all science related methods be it digital or material.

Even though I said he is from year 4000s the answer doesn't have to be accessible in 4000s, time period is irrelevant to the question. I just want to know the possibilities.

EDIT - I have looked on my own, they say it's not possible to compress information infinitely, however the limit wasn't found, so I want a rather high estimate which I couldn't find.

$\endgroup$
20
  • 11
    $\begingroup$ Have you done any research on your own? What have you found? $\endgroup$
    – L.Dutch
    Mar 2 at 17:33
  • 41
    $\begingroup$ Paging Claude Shannon… $\endgroup$
    – Jon Custer
    Mar 2 at 18:43
  • 8
    $\begingroup$ Physically, without reference to any specific storage tehcnology, the most you can compress data is the Bekenstein bound: en.wikipedia.org/wiki/Bekenstein_bound $\endgroup$ Mar 2 at 23:06
  • 13
    $\begingroup$ @JonCuster: A lot of Shannon's work was concerned with transmitting information, especially over a real-world channel with noise (en.wikipedia.org/wiki/Shannon%E2%80%93Hartley_theorem). Compressibility is more the domain of Andrey Kolmogorov: en.wikipedia.org/wiki/Kolmogorov_complexity - essentially, info content as measured by Kolmogorov complexity is the length of the shortest program that could output that data. (Real world compression algorithms are often far from that lower bound on some data sets, e.g. 1 billion digits of Pi doesn't mean anything to gzip.) $\endgroup$ Mar 3 at 5:48
  • 10
    $\begingroup$ @JonCuster: There's also Shannon Entropy, which like Kolmogorov complexity is a way to measure the information content of something. (en.wikipedia.org/wiki/…). So yes, good point, can't ignore the father of information theory! $\endgroup$ Mar 3 at 7:40

8 Answers 8

32
$\begingroup$

Can data be compressed infinitely? No. Thank goodness. Part of the problem is the effort required to compress data represents the effort required to get at it. Thus, the more highly compressed it is the more inaccessible (aka, usless) it becomes. From our sister site, SuperUser we find the following example:

Top performers (based on compression) in this test are PAQ8 and WinRK (PWCM). They are able to compress the 300+ Mb testset to under 62 Mb (80% reduction in size) but take a minimum of 8,5 hour to complete the test. The number one program (PAQ8P) takes almost 12 hours and number four (PAQAR) even 17 hours to complete the test. WinRK, the program with the 2nd best compression (79.7%) takes about 8,5 hours

Decompression is often faster than compression, but it's still a factor you might want to consider. There comes a point where the effort to compress and decompress isn't worth the value, leaving you with the narrative necessity of increasing the limited storage capacity.

Having said that, a comment on that same post on SuperUser points out that a billion-letter notepad file containing a single letter, "A," can be easily compressed to next to nothing while a file containing random characters compresses much less efficiently. That's why you're having trouble finding hard numbers. There isn't a single number guaranteed to represent all types of data and all kinds of files. A datafile, on average, is lucky to see 60% compression. I've seen original TIFF graphic files that couldn't be compressed 2%.

let's talk instead about physical storage. I once had as mementos of my college days, a couple of 1Mb hard drives. They were five inches thick and eighteen inches in diameter. Today that same megabyte of storage fits on a space smaller than the tip of a sharpened pencil.1

Let's combine that with the burgeoning technology of atomic manipulation. That's the ability to manipulate individual atoms. This is something we can't do yet on a practical level, but ignore that. Instead imagine constructing an atomic-level lattice that can be read optically or electrically. The compression of data physically becomes breathtaking. It has been suggested the sum of all human knowledge is approximately 295 Exabytes (an exabyte is 8x1018 bits). However, it shold be noted that humanity's knowledge is expanding at an equally breathtaking rate.

Big Data is growing exponentially. In 2006, the world was generating 161 exabytes of data each year. Just 14 years later, we churn out an additional 2.5 exabytes of data every single day. And while we’re producing loads of data now, it’s nothing compared to what’s coming—for example, storage for the media and entertainment industry alone is projected to grow about 13.3x between 2017 and 2023, and the storage capacity for human genome data is estimated to reach 40 exabytes by 2025. (Ibid.)

To be honest, a lot of that information can, as we say, be compressed. First systemically by removing duplication and making judgements in value. Knowing the dimensions of a bathroom in your home to twenty decimals of precision is, honestly, useless information. Second, through mathematical compression. Let's throw caution to the wind and suggest that in the future we figure out ways to compress better than 2:1. Let's suggest a believable 10:1. Let's then suggests (yup, a lot of assumptions are being made) that the total amount of information that your creation needs is no more than 1,000 exabytes (one zettabyte) of compressed data. Only half jokingly, I'm assuming "the entire knowledge of humanity" needn't include the pictures my little sister drew when she was five years old. Having established that there are limits in usefulness, we're really not dealing with the entirety of human knowledge. Once again... thank goodness.

So, a zettabyte of compressed data going onto an atomic lattice. Ignoring the science (because we're inventing it), let's say a single atomic peak with a ten atom valley in each direction. So we need a space of 10x10 "atoms" to store the data. Taking something somewhat (OK, almost completely) at random, let's asume a mid-sized atom like Antimony, atomic size 150 picometers. A zettabyte lattice would be 1x1021x100*150x10-12 = 1,500,000,000 square meters (if I did the math correctly...). That sounds outrageous until you consider that in terms of today's technology that's one-billion terrabyte hard drives. So, 1,500 square kilometers. Assume we need a nanometer spacing betwee layers of antimony to accomodate our Clarkean data reading system and we get a cube 1.5 meters square.

OK! What did we end up with

Thank goodness for the tag.

  • Assuming a successful data compression rate of 10:1, which is 5X better than we can do consistently today.

  • Assuming "the entirety of human knowledge" can be believably represented by 1 zettabyte of compressed data, meaning 10 zettabytes of uncompressed data.

  • Assuming we can hardwire the decompression process into the data retreival system such that the time it takes to obtain information can be ignored.

  • Assuming atomic manipulation to make the storage medium.

  • Assuming a single bit of data can be read using a volume of 15 cubic attometers.

Your data storage device is 1.5 cubic meters.

However! The important part of this mental exercise is that you can define that volume and the storage it represents to be anything you want. What I've given you is the scientific references you can use to rationalize your choice.


1I might be wrong about this, but if I am, we're darn close to achieving that goal.

$\endgroup$
20
  • 2
    $\begingroup$ You might want to adjust your conversion from pm to m^2, unit conversion is always a pain because when you have >1D units, you've got to multiply the base units too! i.e. 100*150*150*(10e-12 m)^2 per bit (because square units) or about 0.44Exabits/m^2. So you'd need (10ZBytes/0.44Ebits)/(m^2/nm) or half a beer can worth of space... (unit cancellation is weird) But amazingly, a modern 1Tbyte (8Tbit) micro SD card, at 165 cubic millimeters already gets you ~6GBytes/mm^3 or 0.006ZBytes/m^3. You could store that much today with just 1 house worth of 1TB micro SD cards! $\endgroup$
    – Samwise
    Mar 3 at 1:29
  • 3
    $\begingroup$ @Samwise I had a sneaking suspicion... evil units! I'll review the math again tomorrow morning. Thanks! $\endgroup$
    – JBH
    Mar 3 at 2:04
  • 2
    $\begingroup$ You can't make it anything you want. Squish too much information into too small a space, and you'll create a black hole. $\endgroup$ Mar 4 at 1:13
  • 1
    $\begingroup$ if you somehow manage to store 1 bit per atom, and assuming they are antimony atoms with 1 nm between layers for reading (not too scifi - maybe manipulating nuclear spins?), you can store 1.1 ronnabytes of information $\endgroup$
    – Seggan
    Mar 4 at 17:08
  • 3
    $\begingroup$ @LoganR.Kearsley Information content scales with surface area, not volume, today. I've watched microelectronic design shift from single-layer-only (2D) construction to layered (3D-ish) construction and wouldn't be surprised to see true 3D construction before I die. At which point it scales by volume. I've learned the hard way to never assume something is impossible - no matter how much the math and physics say otherwise (see the story of the first 1nm MOS gate, which I was a part of). On the other hand, even if we assume ROM, one must still power the solution and read the bits. $\endgroup$
    – JBH
    Mar 5 at 5:43
30
$\begingroup$

On average? Not at all. It's a simple application of the pigeonhole principle: $x$ bits can convey $2^x$ different messages. $x-1$ bits can only convey half as many messages. You cannot fit all the messages that for in an $x$-bit space into fewer than $x$ bits. So for any message you want to make shorter, there must be some other message that gets longer.

The only reason compression works at all is because we don't care equally much about all possible messages. We only care about a small number of the total number of messages that can fit in $x$ bits where $x$ is really big, so we can take just those messages (the ones that look like meaningful text, or valid image files, or whatever) and re-index them to fit into a smaller bit space. Meanwhile, random-looking messages either don't change at all or get bigger to accomodate compressing meaningful messages. And the better your compression is, the more the output will look like random data, as it should efficiently fill the space of shorter messages entirely with the messages you care about, which means messages you care about should map to a uniform distribution over the space of bit strings. Thus trying to compress something that has already been compressed, and thus looks random, will either do nothing, or make it bigger, on average. And when you have data that you care about but already looks random (like encrypted data), it also cannot be compressed. That's why you should always compress before encrypting, rather than the other way around.

$\endgroup$
2
  • 1
    $\begingroup$ +1 because this answer is the best explanation I've ever read concerning the basic problem with data compression. $\endgroup$
    – JBH
    Mar 2 at 23:48
  • 4
    $\begingroup$ That's why you should always compress before encrypting, rather than the other way around. - if you're going to compress at all, of course. Reasons not to include the fact that the length of a message is often not secret, and in some cases the compressed length can reveal information about the message. Some attacks on SSL / HTTPS have been possible because of compression; see Is there an existing cryptography algorithm / method that both encrypts AND compresses text? for links to details on CRIME and BREACH attacks. $\endgroup$ Mar 3 at 7:33
19
$\begingroup$

Data compression works by removing redundancies, so it depends on what is considered to be "redundant" in the sum of human knowledge.

Lossless compression handles redundancies in a way that allows them to be replicated exactly on decompression. Huffman coding for example works well with repeated strings of data by reducing them to a single figure (a "word" repeated n times and in so many places). Lossy compression on the other hand rerepresents data in a way that removes the stuff that isn't very important. In a jpeg image, high frequency information in the RGB color channels is truncated because humans suck at perceiving color compared to changes in brightness.

Data can't be losslessly compressed infinitely. If you have some algorithm that "compresses" an image down to say two bits, 01, and can faithfully reproduce the original image, then you haven't actually compressed anything. You just moved the information about the image from being in the image container to being in the algorithm. (In this extreme case, something like a lookup table.)

If the sum of human knowledge is one great big text file, then with the best tools you can expect a 4:1 compression ratio.

Compressed files have little redundancies left to enable further compression. They look a lot like binary noise, and any further compression needs to be lossy. Not really possible with plain text unless you reduce the source content (maybe lots of abbreviation, using simplified wording, etc.).

$\endgroup$
5
  • 2
    $\begingroup$ Also note that there are only four combinations of two bits. If you could compress any file down to two bits, how would your decompressor know which of those files to produce? $\endgroup$ Mar 3 at 0:49
  • 4
    $\begingroup$ @ChristopherJamesHuff: This is called the "pigeonhole principle". en.wikipedia.org/wiki/Kolmogorov_complexity#Compression . The shenanigans this answer is referring to (turning data into metadata like filenames but still only counting the length of actual data) have been pulled before, most famously as a loophole in the wording of a compression challenge designed to counter snake-oil salesmen who were apparently common on Usenet comp.compression in the 90s. reddit.com/r/programming/comments/2ybd6i/… has some history. $\endgroup$ Mar 3 at 7:14
  • $\begingroup$ Text files can already compress about 10-to-1 on a good day with the planets aligned. With AI being able to predict the next thing you type, there's a possibility we might be able to improve it more, but probably not better than about 100-to-1. $\endgroup$
    – user253751
    Mar 5 at 13:17
  • $\begingroup$ @user253751 - that wouldn't be lossless compression, though. AI prediction would be lossy. $\endgroup$
    – jdunlop
    Mar 6 at 0:35
  • $\begingroup$ @jdunlop Any source of probabilities (including stupid ones) can be used to inform lossless compression. The better the probabilities are, the smaller the compressed file is. Roughly speaking, LZ-based compression algorithms use a fixed probability model which assumes bits of data that occurred more recently are more likely to occur again, which is a quite reasonable assumption which gives them pretty good but far from perfect properties. $\endgroup$
    – user253751
    Mar 6 at 16:28
9
$\begingroup$

It's sufficient to send a nudge "research this, the result should look like this" and when tuned right, the receiving consciousness should be able to recreate all the knowledge itself.

Consider the kind of tech we already have. For example NVIDIA has already developed extremely low-bitrate video compression for human faces, based on AI. The receiving neural network knows how to animate facial expressions based on its training plus still picture of a face plus little information received.

$\endgroup$
4
  • 1
    $\begingroup$ This answer is underrated and could be elaborated on: If the consciousness does not need the exact words, but rather the abstract knowledge even a work like Shakespeare's McBeth could be reproduced in kind (not perfect) from a small prompt and prior knowledge. - So the limiting factor is the same as in other answers: Computational Power and Time. With this premise the compression can be arbitrarily high if the computational power is arbitrarily high. $\endgroup$
    – Falco
    Mar 4 at 10:38
  • 1
    $\begingroup$ @Falco: Yes in the limit as amount of data stored goes to infinity (every play anyone's ever written, not just compressing the works of Shakespeare). You need some significant chunk of data for the trained model (or whatever else) you're extrapolating from. For faces, that might be significantly larger than an h.264 video decoder. For plays, a model that could produce them from a prompt might be larger than just compressed ASCII text plus the few KiB for a decompressor like xz. Point being, for a finite sized data-set, the model will be some fraction of it. A small fraction for big sets. $\endgroup$ Mar 5 at 7:59
  • $\begingroup$ @Falco Unfortunately you cannot outwith Shannon with infinite computer power. That being said it is true almost all the answers focus on lossless compression which is a severely artificial limitation on the broad question. $\endgroup$
    – Chuu
    Mar 5 at 17:57
  • $\begingroup$ @Chuu I think you can outwit Shannon. For example, if the universe is deterministic (even though current science suggests it is likely not) everything that ever was and will be could in theory be computed from the initial configuration of the big bang. $\endgroup$
    – Falco
    Mar 6 at 20:24
8
$\begingroup$

Information isn't just about what is. Information is also about what could have been. Information isn't just the fact that a particular number, in binary, is 10101110, it's also about the fact that it could have been any one of 255 other possibilities. We measure information with entropy, which is the ratio of what is versus what could have been. The above number is 1 value out of 256. We typically phrase this in logarithmic terms. 8 bits implies 2^8 possibilities (256 possibilities).

When we talk of entropy, we talk about the irreducible aspects of this ratio. If some information has 8 bits of entropy, it means that there is no way to reduce it to anything less than one of 2^8=256 possibilities.

This measure of entropy is the smallest one can compress the information. If you could compress it any more, that would imply that there were fewer possible possibilities in the first place. That being said, entropy for arbitrary information is incredibly hard to calculate. Its entirely plausible that all of the knowledge of humanity might be derived from a single sentence. We've not found one so far. We don't think it comes down to that. But it is theoretically possible.

If some information can be described as the result of a random variable, we can indeed put some numbers on it. If some information describes a dice roll, we know that it has 2.58 bits of entropy (which can be computed from the fact that there are 6 equal-possible outcomes of a dice roll). If one were ever to determine a way to perfectly predict the result of such a dice roll, then we would no longer be able to claim it has 2.58 bits of entropy. It would have less. To date, we know of no way to compress the result of a dice roll.

$\endgroup$
3
  • $\begingroup$ Finally an answer mentioning entropy. Another important point is specialized representations and lossy compressions (JPEG, MP4). A slight degree of acceptable loss -- nigh imperceptible -- may allow a specialized representation to make massive gains on compression ratios. $\endgroup$ Mar 4 at 11:27
  • $\begingroup$ So many interesting comments to a seemingly simple question. The really interesting question is hidden as you say, knowing the true entropy of all human knowledge. You could have an insanely small generator, but if you let it run long enough it would produce the world as we know it. It's such a fascinating area of research and lends itself to beautiful sci-fi :) $\endgroup$
    – Hakaishin
    Mar 4 at 16:03
  • $\begingroup$ @Hakaishin: "true entropy" (the smallest you can make something with optimal compression, including compression specific to that kind of data) is called Shannon Entropy: en.wikipedia.org/wiki/… . It's related to Kolmogorov complexity, which includes the size of the decompressor, i.e. smallest program that can print the result. Shannon was concerned with communication systems where the compressor / decompressor are used with an arbitrary amount of data so their size is negligible. $\endgroup$ Mar 5 at 8:04
0
$\begingroup$

Currently, the most compound storage in existence is the brain. All of 'the internet' combined could be concentrated into a space the size of an oil tanker. (This may be outdated.) This storage, despite it's immense size, could not store the information of a single human brain, let alone all of them.

From an engineering perspective, your most 'realistic' solution, is to construct a matrioshka brain, a device that uses the whole energy output of the sun for computing, and then you want to find a way to create computing smaller than a brain, which might be possible if there are use able particles smaller than qubits. Or you could just keep a copy of everyone's brain, powered directly by the star. Then using that same star, you can constantly shoot out a tight beam of energy towards your 'Avatar' who can then receive it. Depending on the reliability of this, and the distance, this could become a new plot device, as your main character may need to wait for vital information, like how we have to search sometimes to remember things.

$\endgroup$
3
  • $\begingroup$ This should be a book, definitely seems more supernatural though... $\endgroup$
    – Zautech
    Mar 4 at 20:13
  • 1
    $\begingroup$ How do you know the storage capable of containing the internet could not store the information of a single human brain? Certainly we do not (yet?) know how to do this; but I don't believe we currently know it's not possible. I wouldn't be surprised if the human brain turns out to compress very nicely given the right insights into how it works. $\endgroup$ Mar 5 at 0:47
  • $\begingroup$ @DanielWagner: I assume this is based on the number of theoretically possible states / arrangements for a brain with that number of neurons, not limited to ways that make a human brain capable of "normal" thought, vision, etc. So you get a huge information capacity if you could use quantum tweezers to put each neuron into a state you select and later read back those states somehow. $\endgroup$ Mar 5 at 8:07
0
$\begingroup$

How much you can compress information depends a lot on the type of information you're concerned with. You can contrive absurdly high compression ratios in a plain English representation by, for example, describing "a string of 30 quintillion A's", which has a compression ratio of exactly 1 quintillion to one. I can't even write that string because it's far too big for any consumer-grade computer to store.

But that's probably not what you're thinking of because that's not particularly useful to have a ludicrously long string of A's.

The Complete Works of William Shakespeare is 2.5MB zipped and 6.9MB in plain HTML, for a compression ratio of about 2.76:1. Thing here is that HTML is an especially redundant data format, so it compresses better than plain text would, but at the same time, there probably aren't that many tags, so for plain text Shakespeare might fall somewhere around 2.5:1

I think it's safe to assume that most literary written works would compress somewhere in this neighborhood. You could maybe do a little better with fancy algorithms available in the year 4000, so optimistically, we'll say 3:1 on average for literary works.

Technical writing, which the sciences would be based on, tend to be much more information-dense, and would thus may be limited to lower compression ratios. But it's also not that big of a difference, so we'll go with 2.8:1 for technical writing and scientific papers.

Audio and video compress pretty well because we can afford to lose some information because we won't notice the small differences anyway. Audio can be compressed to somewhere just shy of 6:1 (with MP3, though Ogg is similar) before it becomes noticeable, and you can probably go up to about 8:1 before it could be, in a sense, comparable to the quality of a human memory of an audio clip. (not that I have any data or science to back that assertion) A 720p 24fps video compresses pretty nicely (unless there is confetti) to 12.5Mbps, for a compression ratio of 56.6:1. Assuming future algorithmic improvements, you could maybe get that up to 60:1 or perhaps even 100:1 if some algorithm can get really good at throwing out detail where you typically wouldn't pay much attention.

Realistically, you're not going to be able to do much better than this. It's just not mathematically possible unless you can settle for some extremely lossy compression schemes.

It would not be possible to encode the entire body of scientific and literary knowledge into a single person's brain. I don't think you, or anyone for that matter, fully understand how many books and scientific papers have been published in just the last 100 years. You're going to have to be very selective about what information gets crammed into that brain.

$\endgroup$
-2
$\begingroup$

You can PI compress. As in a number to a digit start in PI and a length. https://github.com/1184893257/PiCompress

Its horrifically slow.https://en.wikipedia.org/wiki/Chudnovsky_algorithm gets you O (n(log n)^3) as time complexity.

You can also compress a file into a game of life start pattern + cycle counter and overlay several of those in boolean operations.

https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

If you use e/Pi/ Constant Snippets as game of life start patterns, you can get pretty low, pretty fast.

http://www.shodor.org/media/content/petascale/materials/UPModules/GameOfLife/Life_Module_Document_pdf.pdf

You can also parallelize the game of life- due to it being a "physical simulation" meaning- it has a c constant at which information can affect other information within the Game of Life. So if you merge your file together from small clusters its pretty parallizable.

$\endgroup$
5
  • 7
    $\begingroup$ "Pi compression" usually requires at least as many bits to store the index into pi. For instance, atractor.pt/cgi-bin/PI/pib27Search_vn.cgi finds "ROMEO" at position 71116480, which is 26 bits, while naievely encoding "ROMEO" in base-26 and converting to base-2 is 24 bits. (You can do a lot better with eg huffman coding) $\endgroup$
    – Kaia
    Mar 4 at 20:17
  • $\begingroup$ Without going into the details: Is there a proof that any string of digits can be found in Pi? Maybe try to replace the first 3 with 4 and then find the result in Pi... $\endgroup$
    – U. Windl
    Mar 5 at 10:15
  • $\begingroup$ @Kaia - that is a a pretty rare edgecase though? Nobody compresses small stringlets.. $\endgroup$
    – Pica
    Mar 5 at 14:01
  • 1
    $\begingroup$ @Pica I believe the logic is the same for any length of string. There are 2^n bitstrings of length N, so in expectation you'd find the index of that bitstring at 2^n bits into pi, so the index takes N bits to express too. $\endgroup$
    – Kaia
    Mar 5 at 18:09
  • 4
    $\begingroup$ (Maybe a more convincing argument: If it were possible to compress arbitrary strings using Pi, you could do it recursively to achieve arbitrary compression: find the index-into-pi itself in pi, and the index of that, and so on. so it's ruled out by the pidgeonhole principle) $\endgroup$
    – Kaia
    Mar 5 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .