Fun with computer science in Kaiba


I’d been rewatching Kaiba with a bunch of people a while ago. Kaiba’s a great show to watch if you want to talk about things, especially if you like dealing with the sorts of moral and ethical issues that come about in a world that’s so starkly different from ours. The obvious things to talk about revolve around identity and existence. Being the computer scientist and the guy who likes to make laboured analogies to things I like, I began to think about memories and cognition from a CS point of view.

Kaiba’s already done a lot of the “what if” in exploring the idea of memories that are as easy to work with as data on today’s computers. There was an observation in one of the episodes that it seemed like one of the characters’ had too many memories and seemed to be unable to create anymore since there was no more room to store them. The obvious answer to me seemed to be just to throw in another disk or something. Of course, another thing we can do, since we can manipulate memories like data, is to selectively choose less important things to throw onto that extra “disk”. In a way, that’s kind of like what we do already, except instead of having a machine suck out our memories, we do things like write them down or take pictures of them. And in the case of photos, it kind of is like having a machine suck a memory out. In either case, that relieves us of the burden of having to keep it in our brain.

In light of this, it’s kind of a good thing that our brain cells do decay eventually and we do forget things. Otherwise, without a way to manipulate our memories like they do in Kaiba, we’d actually run out of room. Usually, we like to think of data or information as this ethereal sort of thing, but realistically, it’s constrained by the physical world. Those bits have to be written down somewhere, whether it’s on a magnetic platter on a hard disk or in a cell in our brains or in a photon in a quantum computer or in a weird capsule like it is in Kaiba.

Recently, someone linked to something about solving NP-complete problems in polynomial time by taking advantage of the many-worlds interpretation of quantum mechanics. This lead me to some of Scott Aaronson’s papers. Scott Aaronson is a complexity theorist who does quantum stuff at MIT and writes a neat blog. I read through the lecture notes for this course he did while he was a postdoc at Waterloo called Quantum Computing Since Democritus and a paper called Why Philosophers Should Care About Computational Complexity. These two things attempt to tie computational complexity and quantum computing with philosophy (duh). The Democritus stuff is pretty accessible if you have a bit of mathematical background and it introduces concepts like computability, complexity, and quantum computation if you’re not familiar with them. The complexity for philosophers paper assumes you’ve done some computational complexity.

So in Kaiba, we can send our minds around and stick them in other bodies or even in machines. But if we can stick them in machines, what’s running it? We’re not sure, but if we can build machines to interface with our minds or run those processes, then we’ve got a computer that can simulate our brains. This is where computational complexity comes into play.

Aaronson notes that a lot of people who think they consider AI a metaphysical impossibility really haven’t thought it through that far and are only considering the practical impossibility. For instance, what can we extract from the fact that Kaiba has computers that can simulate brains? One thing is that simulating a brain can be done efficiently, presumably in polynomial time.

See, in computer science, a lot of things (like simulating a brain) are possible if you just hardcode everything into a lookup table. Luckily, like I mentioned before, there’s a finite amount of stuff we can hold in our heads. So yeah, you could simulate a brain like that and it’ll work because the table’s finite, but you’d probably run out of atoms in the universe to hold all of that data and the possible choices that would branch out that the computer could make as it went along. Of course, that’s only a practical concern.

Which is why Kaiba’s brain simulating must be efficient, otherwise it wouldn’t be physically feasible. This would seem to imply that simulating a brain didn’t turn out to be that hard. Of course, this means that we’ve got a way to formally describe and model the way brains work too. Anyhow, this is all to ask, if we did have a way of doing this, would a computer simulating a person be that person? And then, we can go a bit further and ask whether a person that we’ve fabricated the data for and is simulated by the computer also constitutes a person.

It’s kind of the same question as whether clones would be people, isn’t it? Except instead of creating perfect copies of the entire person, we can just create perfect copies of the person’s memories and throw it into a computer. Of course, this leads us to the implication that brains are deterministic. Otherwise, this entire memory transfer thing wouldn’t work. You wouldn’t be able to designate a person as their memories if how they behaved changed with the brain that they occupied.

We do have some indication that the brains seem to function differently based on the body that they’re controlling. When Kaiba is in Chroniko’s body and meets the girl who’s in the huge guy’s body, they mention something about getting used to the body. It does make sense that biological processes are governed by the brain and isn’t tied to the person’s identity, but then we see how the body interacts with the person when they start to have ~feelings~ for each other. Of course we can consider the body as another part of the input into the brain and then that discrepancy goes away.

So the thing is that in Kaiba, we’ve got a way of creating something that’s literally indistinguishable from a person. Well, okay, we did start with the premise that it’s possible to simulate a person’s brain, which is kind of a stretch in the real world. But now we ask, what properties would human consciousness need to have in order for a computer to be unable to efficiently simulate it?

It turns out there are some possible ways for this to happen. For instance, if we could solve NP-complete problems or do quantum computations, then a classical computer wouldn’t be able to simulate our brains. Of course, that’s assuming P≠NP, so if it turns out that P=NP, then we might have to rethink this condition, and a quantum computer will be able to do quantum computations, so if we ever built one of those, then that also reduces our options. And of course, the bigger problem is that it assumes we can solve NP-complete problems or do quantum computations in our head.

On a slight tangent, this idea of quantum computations in our head leads to the question of what happens if our brains stored quantum information. That would make it very difficult to make perfect copies of our memories because of the no-cloning theorem in quantum information. The theorem is exactly what it sounds like: it’s impossible to make a perfect copy of an unknown quantum state. What this would imply is that if you tried to make a copy of yourself, it would not be 100% identical to you. Admittedly, it’s pretty unlikely that our brains can store any quantum information.

To close, something that’s slightly related, since it happened around the same time as I was watching, was a department seminar I went to where the guy was talking about neuroscience and brain imaging and tying it into graph theory. Essentially, what he did was he took a bunch of MRI scans of someone’s brain and created some graphs on them somehow. He then ran a bunch of algorithms on the graphs for a bunch of metrics to see if graph theory were any use for neuroscience purposes.

What he found was that the brain activity that could be seen from the scans translated to changes on the graph. Those graph transformations acted on the graphs in a predictable way from the metrics. He raised the possibility of linking thought or computations in the brain with graph transformations. The nice thing about graphs is that, even though there are plenty of problems that are hard, we still know a lot about them and we’ve got a ton of graph algorithms already.

Who knows, maybe we’re further along in figuring this brain thing out than we might think.

The Future Gadget Lab vs. Kolmogorov complexity


In Steins;Gate 12, the Future Gadget Lab is faced with a problem. They need to send a copy of a person’s memory, or about 3.24 TB, to the past, but they can only send 36 bytes. What is a MADDO SCIENTISTO to do? What they end up doing is sending that data to the Large Hadron Collider to compress with a black hole. Problem solved! Or is it?

Obviously, using a black hole to compress data is silly, since a black hole would probably just destroy the data. In fact, it’s probably unnecessary, since if it were physically possible to achieve that kind of compression, you’d be able to do it on any computer because of the Church-Turing thesis. The only thing that would change is how quickly the algorithm would run. Luckily, in theoretical computer science, when dealing with the question of whether something is possible or not, we don’t care how long it’ll take. So, is there a compression algorithm that can give us the desired result?

Basically what we’re doing when were compressing stuff is we’re trying to rewrite a bunch if zeroes and ones, or strings, into a smaller bunch of zeroes and ones that mean the same thing. In general, this is impossible to do, since there are less strings of zeroes and ones when you have less digits, so you can’t arbitrarily stuff, say eight bits of information into seven bits. What you can do is create a way to describe the zeroes and ones in a way that is smaller than what you start out with.

For instance, we can describe strings of zeroes and ones in plain English. It’s shorter to write “one hundred zeroes followed by one hundred ones” than writing


The obvious problem with our compression scheme so far is that there are some strings that are not very easy to describe and it might be longer to describe in English than it would be to just write the bits themselves.

Again, it appears to be difficult to create a compression scheme that works for any old string. It’s much easier to create such an algorithm when you know something about the kind of string you want to compress, like if it’s a certain size or if it has any patterns or something. In the case of the FG lab, we know they won’t need to worry about compressing strings of length 288 or less. Unfortunately, there isn’t much more we know about the strings they want to compress other than the fact that they’re huge.

Actually, there’s another problem, which is that they need a way to decompress the string they’ve sent. If I give you a description of the string in English, it’s not going to do you any good unless you already know English. So in addition to sending a compressed string, they need to send information about the compression scheme they used, all in 36 bytes.

In information theory, the length of the shortest description of a string $x$ is its Kolmogorov complexity, which we’ll denote $C(x)$. Formally, $C(x)$ is defined in terms of encodings of Turing machines that generate $x$, but it’s pretty easy to argue that the choice of how we describe $x$ doesn’t matter up to a constant term.

We know that $C(x) \leq |x| + O(1)$ (where $|x|$ is the length of $x$), since we can always just write out $x$. We also know that for every length $n$, we can always find a string $x$ such that $C(x) \geq |x|$ since there are $2^n$ strings of length $n$ but only $2^{n-1}$ shorter descriptions of those strings. These strings that can’t be compressed are defined to be random.

We can quantify this idea of compressibility by saying that a string $x$ is $c$-compressible if $C(x) \leq |x| – c$. And so, we can argue about how likely it is that we have a string that can be compressed to the degree that we want. For strings of length $n$, we have that at least $2^n – 2^{n-c+1} + 1$ of them are incompressible by $c$.

We have some numbers, so let’s play around with them. Remember from earlier that the approximate size of Okarin’s memories is 3.24 TB, or $3.24 \times 2^{40} \times 8$ bits, while the limit we can send is 36 $\times$ 8 = 288 bits. If we want to squeeze Okarin’s memories into a text message, we’ll have
$$c = 3.24 \times 2^{40} \times 8 – 288 = 2.849934139166592 \times 10^{13}.$$
WolframAlpha helpfully tells me that this is slightly more than 1.4 times as many red blood cells in the human body.

We can calculate the probability that we have a compressible string by figuring out the probability that incompressible, which we can do with our lower bound on the number of incompressible strings we have. Taking $n = 3.24 \times 2^{40} \times 8$, the probability is given by
$$1 – \frac{2^n – 2^{n-c+1} + 1}{2^n} = \frac{1}{2^{c-1}} – \frac{1}{2^n}.$$
Plugging our numbers in, we get
$$\frac{1}{2^{3.24 \times 2^{40} \times 8 – 288 – 1}} – \frac{1}{2^{3.24 \times 8 \times 2^{40}}}.$$

And unfortunately, after this step, WolframAlpha kind of refused to try to do the computation. I gave it a shot on my laptop in Python but all that happened was CPU usage went up to 100% for a few minutes and it started eating all of my memory. I kind of wanted to keep using my computer instead of waiting it out for a MemoryError exception, so I interrupted it. Doing some further estimation, I threw $2^{2^{40}}$ at WolframAlpha, since it’s kind of about the same neighbourhood in magnitude as the number we’re trying to get. Apparently, it’s a number that’s about 300 billion digits long, so one in that are the kind of odds you’re looking at.

I guess this is another way of saying there’s no chance in hell that what the FG Lab tried to do would ever work. And remember that we’re not talking about any particular compression algorithms or technologies here. We can’t come up with a better algorithm or scheme. We can’t use faster computers. We can’t use quantum computers (Holevo’s theorem says that we can’t, in general, use less qubits than classical bits for the same string). From an information theoretic standpoint, it is impossible.

But I’m pretty sure everyone already could’ve guessed that anyway.