「希望」/「niuya」

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.

「Steins;Gate」/「いさりび」

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

00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111

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.

A combination of an incidental argument over whether the cast of Sesame Street or the Muppet Show would win in a fight and reading about Internet crazy people refusing to believe the uncountability of the real numbers lead to this. I hope you like math.

So we know that Count von Count (colloquially known as The Count) loves counting. According to Wikipedia, he will count anything and everything, regardless of size, amount, or annoyance he causes everyone else. The logical question would be, what happens when we present The Count with an uncountable set like the set of real numbers, ℝ (unless you are a crazy person)? Can he count it?

The answer is of course he can, he’s the goddamn Count.

What are the implications? Basically, The Count can enumerate any set, whether it’s uncountable or not. This means that to The Count, every set is recursively enumerable. This means that for every set S, S and its complement S’ are recursively enumerable. But this means that every set S is recursive.

So, now we consider the halting set H = { (P, w) : program P halts on input w ∈ Σ* }. From above, we have that H is recursive (since H’ is recursively enumerable). But this means that H is decidable. This means that The Count can decide the Halting Problem, and thus, can decide any undecidable problem.

What we conclude is that The Count’s power isn’t to count, but is, in fact, to break logic.

By popular demand, here’s a post that’s not about animu. Let’s see what delights my 3B term is bringing me.

CS 462: Formal Languages and Parsing (He)

This was one of the courses I was most looking forward to. And then I found out the prof I that I thought was teaching the course (who is a really awesome prof) was going on sabbatical. щ(ﾟДﾟщ)

The actual prof isn’t that great in lecture. His speaking isn’t very good and neither are his board notes. He’s pretty good when emailed though, so I just read the textbook and imagine it’s the author (who was the prof I wanted to get) lecturing instead and I just take notes.

The course itself is pretty cool. It seems to be more CS 360 stuff and in the same order too, going from finite automata and regular languages to context free languages and then to Turing machines. Thank God for Jeffrey Shallit’s book, A Second Course in Formal Languages and Automata Theory. I think I’m going to keep it.

CS 466: Algorithm Design and Analysis (Biedl)

This is another really cool course. In terms of content, it seems like it’s just more CS 341: here’s a problem, now let’s try to solve it and refine the solution. Now, we have a few more techniques that didn’t make it into CS 341.

I really liked the prof for this course when I took CS 360, enough to change my plans and push STAT 231 even later. But, having Timothy Chan guest lecture one class sort of convinced me I probably would’ve been okay if I’d decided to hold off on it until spring. Still, really good prof with really good board notes, although I find her equations and formulas really, really verbose. This preference for verbosity over notation seems to be a thing that’s really common among CS profs, actually.

PMATH 352: Complex Analysis (Spronk)

This was probably the class I was most worried about, since the last time I had anything to do with calculus was in 2A, which was two years ago. And it turns out my fears were completely realized. The class itself seemed pretty interesting, but it became clear that I had no idea what was going on when the time came to do assignments.

The prof was really helpful when I talked with him about it. This eventually lead to me dropping the course on his suggestion and altering my program plan to a more achievable one. He’s also really good in lecture and is one of those profs that proves and notes every detail. He writes really fast though.

PMATH 432: First Order Logic and Computability (Csima)

So I learned too late that I probably should have chosen PMATH 434 (Computational Number Theory) over this one. The course content for this was essentially a more intense version of CS 245 combined with what I believe will end up being the solvability parts from CS 360 and CS 341. Well, the stuff on solvability might make it worth taking this course, so we’ll see. This course is also kind of annoying because there’s always something that I’m missing in a proof that causes me to hemorrhage marks.

The prof is alright and has pretty good board notes, although she does get mixed up a bit sometimes. I don’t blame her, when you’re going on about models of stuff and interpretations of stuff, it’s not easy to keep track of it.

PMATH 442: Fields and Galois Theory (Liu)

Best course of 3B. Remember when I said rings and fields were awesome and groups were kind of meh? Well, Galois theory tells us that groups can be alright. It just takes something interesting like fields to make groups cool, that’s all. So yeah, field theory (and by extension, ring theory) is pretty awesome.

The prof for this course is great. Her accent needs about one class to get used to and then you’re good. Best board notes of the term. The thing that sets her apart, though, is that she cares about the students. She’s always asking us for our opinions on things about the class and tries to make sure that we understand everything and reminds us that if we’re having trouble, we can always ask her for help and stuff.

Even though my carefully crafted course sequences were thwarted, I’ve gotta say that 3A has been my most enjoyable term so far.

PMATH 346: Group Theory (Lawrence)

I was expecting this to be as killer and awesome as PMATH 345. Fortunately, it wasn’t as killer, because the prof was nicer to us on the midterm. Unfortunately, I don’t really like groups as much as rings. Oh well, still pretty fascinating. In theory, groups come before rings, but rings are so much cooler. The prof is pretty good.

PMATH 340: Elementary Number Theory (Ingram)

I was expecting this to be easy and interesting. I was right about the easy. The first half of the course was essentially MATH 135 over again. I didn’t think the prof’s lecturing was terribly interesting, but he had excellent course notes which allowed me to not go to class. I would have loved to have Vanderburgh though.

CS 360: Introduction to the Theory of Computing (Biedl)

This class is pretty awesome and the prof is pretty awesome. One of my favourite classes, this one starts with finite automata and regular languages, moves on to context-free languages and grammars, and ends with Turing machines and solvability. It wasn’t hard to pick up the material and it’s super interesting. The prof is so awesome that I reworked my course sequences so that I could take CS 466 (Algorithm Design and Analysis) with her.

CS 341: Algorithms (Shallit)

This is also another fascinating course. Basically, the course is structured so that in the first part, you go through techniques to design algorithms and examine problems and various algorithms to solve those problems. After that, you move on to looking at lower bounds on problems. Then, you have a look at graph problems: minimum spanning tree and shortest path algorithms. The final part of the course is the most interesting, looking at complexity classes and NP-completeness in particular. The prof is also really awesome. I’m looking forward to having him again for CS 462 (Formal Languages and Parsing).

CS 350: Operating Systems (Aboulnaga)

Operating system theory is kind of interesting, but not enough to keep me concentrated after the other two CS lectures. Oh well.