oh github pages

I didn't realize it, but the little webpage http://dglittle.github.com/smiley-slider on github that shows the smiley-slider in action had been broken. Whenever people would go to dglittle.github.com/smiley-slider, they would be redirected to glittle.org/smiley-slider, which was nothing -- a 404.

This redirection happened as a result of me setting up my homepage glittle.org to be served from github, which involved having github redirect dglittle.github.com to glittle.org. Apparently this breaks all my project pages.

This behavior is apparently foretold in a tip at the bottom of this article. Paraphrasing, it says: project pages like dglittle.github.com/smiley-slider will be redirected to things like glittle.org/smiley-slider unless they have a file telling them to redirect somewhere else. Of course, the very next tip says that they won't actually be redirected anywhere if there is such a file.

Which is strange. But great. It means that maybe I can fix my problem by adding a file to the smiley-slider repo telling it to redirect to some bogus domain, like example.com (except specifically not example.com, since github knows that that domain is bogus), which would cause it not to redirect anywhere. In particular, causing it to not redirect to glittle.org/smiley-slider, which is nothing -- a 404.

This did work. Sortof. I thought the behavior would be that it wouldn't redirect dglittle.github.com/smiley-slider anywhere, but the actual behavior is that it does redirect dglittle.github.com/smiley-slider to glittle.org/smiley-slider just like before, except that miraculously, glittle.org/smiley-slider shows the content held in the smiley-slider repo. And I have no idea what it would show if the homepage repo happened to have a directory called smiley-slider.

Anyway, I'm confused, but it seems to work. However, this means I need to put a bogus file in all my projects telling github that they are being served on some domain that they are not being served on. I suppose one alternative is to have my homepage in a regular project, so it doesn't cause dglittle.github.com to redirect, but that would mean having my homepage it a github branch called gh-pages, rather than master, which seems confusing, but maybe less confusing.

[update: now I do have my homepage in a regular project so it doesn't cause dglittle.github.com to redirect]

DotTracker

..going through old crap, I found this "DotTracker" program. It's something I wrote in undergrad for, um, tracking colored dots in video. Here's a description of the algorithm I found in a file appropriately labeled "writeup of algorithm.txt", though I can tell it's a rough draft, because the file has above it some text where I was obviously writing a new/better description, but never finished:

Orange Dot Tracking Algorithm

Consider a "tracker" to be an object capable of tracking a moving dot in a video sequence.

The tracker is defined by a center, a color, and a size:

center - the x,y position of the tracker within a frame of video; this variable is updated every frame

color - the color that the tracker is tracking; this variable is initialized to the color of the pixel that the user clicks on when "placing" a tracker. This variable NEVER CHANGES once it is initialized.

size - the algorithm essentially examines a square set of pixels centered around the "center" of the tracker; the "size" variable defines the size of this square.

The crux of the tracking algorithm is an update function which centers the tracker on a splotch of color.

Here's an image in that directory that I used for testing. Note that the dots on my arm are not orange, but green. Apparently the algorithm could track any color, not just orange ;)

The code is now on github: https://github.com/dglittle/DotTracker

reduction

When talking about computer sciency problems -- the sort of problems that people like to call NP-complete and such -- people often say things like "problem A can be reduced to problem B".

The word reduce is confusing to me.

This "reduction" makes it sound like a large problem called A is becoming smaller -- reducing in size -- so it can fit somehow in B.

But that's wrong. B is generally a bigger and harder problem than A.

For example, we might "reduce" the problem of finding the maximum number in a set of numbers to the problem of sorting the numbers. That is, we can sort the numbers, and then we'll get the maximum number for free by looking at the last number in the sorting. But sorting is harder than finding the max, so we didn't really reduce the size of the problem of finding the maximum number when we sorted the numbers -- we did more work than we needed to.

So, I propose that we stop saying "reduce", and saying something like "embed" or "express in terms of".

I can embed the problem of finding the maximum number into the problem of sorting numbers, or I can express the problem of finding the maximum number in terms of the problem of sorting numbers.

arguing

My uncles have lively discussions -- arguments one might call them. I have inherited the trait of enjoying arguing, and I can get pretty emotionally vested in them.

My philosophy of arguing changed a bit when I did debate in High School. Since I was forced to argue both sides of each topic, I grew to feel that both sides of every argument were "right". Of course, the topics tended to be chosen for having good points on both sides.

In any case, I'm not sure whether both sides of an argument are "right", but here's a made-up word-to-the-wise about arguing:

You can only truly win an argument if you can argue in favor of your opponent's side better than they can.

homesick sentimental scenes

Occasionally I get this feeling of.. not sure what to call it.. homesick? sentimental? It's a good feeling. I think. I can't quite put my finger on it.

Anyway, here are some situations, mental images, where the feeling comes up for me:

1. The image of a car in the country leaving home, at night, on a long journey.

2. Cars in the rear view mirror on the freeway at night, with their headlights reflected on the freeway surface.

3. Outside a high, flat, featureless wall of an arabian night's style building, at night with the moon shining, where the whole scene is clean and pristine, and nobody's around.

4. Being inside a car during a rainstorm.

I see a couple themes here: cars and night time.

singularity

I had a little conversation with a friend today about the "singularity" -- the name commonly given to the idea of what will happen to humanity as people can be wired together with computers, and computers become powerful enough to simulate human level intelligence.

A couple things occurred to me. First, although I believe that something like the singularity will eventually happen in reality, I also want it to happen, and so it's hard to know if my belief in the singularity is distorted by that desire, in the way some people might accuse religious people of just wanting religion to be true so they don't think life is meaningless.

Second, I have a somewhat unconventional view of my hopes for the singularity. A lot of people who believe in the singularity see it as a way for man to become immortal, which is an appealing way to avoid the modern "scientific" belief that death is the complete end of a human's existence.

I don't have that belief though. I told my friend that I wasn't concerned if I made it to the singularity or not. And he pressed me about why. And it forced me to articulate my reason, which is this: I'm not sure I'll make it to the singularity. I might die first. And I can't prevent the possibility of my death, no matter what I do. So I want a view of the singularity that makes it "ok" if I die tomorrow.

Incidentally, my belief -- that makes it "ok" to die tomorrow -- is something along the lines of believing that the universe is on a course toward greater intelligence, which is somehow weirdly inevitable by the laws of nature -- the strange force that causes life to arrise and tend toward more complex and interesting life. And I am a part of that. I am programmed to act as a sort of neuron in the brain of humanity, and I can't help myself but do that. That is, whether I like it or not, it seems like that's what I do, and I've decided that I like it. It makes me less concerned about what happens to Greg, allowing me to concentrate more on "solving problems", which is what my programming tells me to do anyway (which is a bit circular I realize, since no matter what I do, or what viewpoint I take, I can say that's what I'm programmed to do...). Anyway, I need to think about this more to articulate what exactly I find appealing about it...

double-slit experiment

This post attempts to model the double-slit experiment with a very simple quantum computer. That way, we won't understand the weirdness, but at least we'll see some simple math that reproduces it.

This post is an update to a previous post, and it may be helpful to read that one first.

The double slit experiment convinced me that quantum stuff was weird. The experiment goes something like this. We shine a light at two thin slits near each other, and we expect to see two thin bars of light on the other side. However, somehow the thinness of the slits causes the light to spread out, as if the photons are hitting the sides of the slits and being deflected. But that's not all. If the light just spread out behind each slit, we would expect to see two wider patches of light, but instead we see many bands of light.

The common explanation is that the light is behaving like a wave, where the bands of light are analogous to water waves from two pebbles dropped in a lake interfering with each other.

However, if we dim the light so that only one photon is going at a time, we still see the interference pattern. This is weird because it suggests that a single photon must somehow be going through both slits, and then interfering with itself.

At this point, someone got the bright idea to try and detect which slit each photon went through. I don't know how they do that. It seems impossible to "see" a photon. But they manage, and when they do, they see the photon go through one slit or the other, but the interference pattern goes away. This leads people to scratch their heads and say things like "quantum stuff is all crazy and wave like until you observe it, and then it quickly shapes up and acts normal".

Simple Model

Now let's model what's going on with a simple quantum computer. This section will be easier to understand after reading this post, and will use the random and copy gates from that post.

At first, our computer will involve a single qubit. This qubit represents the photon. The qubit can be 0 or 1. We'll say that 0 is analogous to a photon in the double-slit experiment going through the first slit, and 1 is analogous to the photon going through the second slit.

Next, we need to model the "spreading out" of the photon after it goes through a slit. We'll do this with a gate called half-random. The gate works like this: if we send a 0 through it, then it will probably stay a 0, but it might change to a 1. If we send a 1 through it, then it will probably stay a 1, but it might change to a 0. This is meant to represent a photon going through a slit and probably hitting the wall directly behind that slit, but maybe hitting somewhere else.

The matrix for the gate is [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]]. We can model sending a 0 through it, by first recalling that a 0 is represented with the state vector [1, 0], and then doing some matrix multiplication [1, 0] * [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]], which is [cos(π/8), sin(π/8)]. If we square each element to get the probabilities, we get [0.85, 0.15], which is an 85% chance of seeing 0, and a 15% chance of seeing 1. If we send a 1 through it, I swear that the opposite happens: there's a 15% chance of seeing a 0, and an 85% chance of seeing a 1.

Now we just need something to simulate firing a photon at the two slits such that we don't know which slit it goes through. We'll do this by taking a qubit and sending it through a random gate. The matrix for this gate is [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]]. If we initialize our qubit to 0 and send it through this gate, it enters the state [sqrt(.5), sqrt(.5)]. When we square each element to get probabilities, we get [.5, .5] which is a fifty-fifty chance of being a 0 or a 1, which seems random enough.

So what happens when we send a qubit first through random, simulating firing a photon at the two slits and not knowing which one it went through, and then sending the qubit through half-random, simulating the photon "drifting" from the slit it went through before it hits the wall? I claim that if this wasn't a leading question, people would guess that it would remain a fifty-fifty split between 0 and 1, since a 0 has as much chance to drift to 1 as a 1 has to drift to 0.

Let's try it. We initialize our qubit to 0, which is the state [1, 0]. After it goes through random it becomes [sqrt(.5), sqrt(.5)], as we saw above. Next we multiply this by the half-random matrix like so [sqrt(.5), sqrt(.5)] * [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]], yielding [0.92, -0.38]. When we square these we get [0.85, 0.15], which is an 85% chance of seeing a 0, and 15% chance of seeing a 1.

I claim that this strange non-even distribution of probability is analogous to the interference pattern we see in the double slit experiment. Of course, with the light, there are many places each photon can end up on the wall, so there is room to create fancy looking interference patterns. In our simplified version, there are only two places the qubit can end up: 0 or 1. So really, anything that isn't a fifty-fifty split is as close to a "fancy interference pattern" as we can get.

Observation

We want to simulate observing which slit the photon passes through. We could do this by simply opening the qubit after passing it through the random gate. This would force it to be a 0 or a 1, and when we sent it along through the half-random gate, that gate would behave as expected, without any interference pattern. But somehow this feels like cheating. It feels like someone stopping the photon before it passes through a slit, and then sending an entirely new photon out the back of the slit toward the wall.

Somehow we want to "observe" the qubit without actually opening it. We can do this with a copy gate. We'll send a qubit through random, then we'll send that qubit along with a fresh 0 qubit into copy. Now we have two copies of the first qubit, or as close as we can get, so we can send one through half-random, and we can open the other one to see what the qubit was before sending it through half-random.

The first half of this we've already done in the previous post, sending one qubit through random, and then copying that qubit. The result is: [sqrt(.5), 0, 0, sqrt(.5)], which is a 50% chance that both qubits are 0, and a 50% chance that both qubits are 1.

We saw before that we can't decompose this into a state vector for each qubit, i.e., they are entangled. So we need to treat the action of sending one qubit through half-random and leaving the other qubit alone as a single gate. We can model "leaving a qubit alone" with a do-nothing gate represented by an identity matrix. Next we need to do some Kronecker product magic to combine the matrices for these gates together: [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]] ⊗ [[1, 0], [0, 1]], which yields [[cos(π/8), 0, sin(π/8), 0], [0, cos(π/8), 0, sin(π/8)], [sin(π/8), 0, -cos(π/8), 0], [0, sin(π/8), 0, -cos(π/8)]].

Now the moment of truth. We multiply our state vector [sqrt(.5), 0, 0, sqrt(.5)] by the large harry matrix we just created like so [sqrt(.5), 0, 0, sqrt(.5)] * [[cos(π/8), 0, sin(π/8), 0], [0, cos(π/8), 0, sin(π/8)], [sin(π/8), 0, -cos(π/8), 0], [0, sin(π/8), 0, -cos(π/8)]], giving us about [0.653, 0.271, 0.271, -0.653]. If we square these values we get about [0.427, 0.073, 0.073, 0.427]. These probabilities are associated with the states 00, 01, 10 anad 11, where the first bit in each state represents the first qubit which went through the half-random gate, and the second bit represents the second qubit which we left alone.

So what is happening here. If the second qubit is a 0, meaning we think that the first qubit was a 0 before entering the half-random gate, then there's a 0.427/(0.427 + 0.073) ≈ 85% chance that the first qubit is a 0. This is what we would expect if the first qubit really was a 0 before entering the half-random gate. So no interference so far. Also, if the second qubit is a 1, meaning we think that the first qubit was a 1 before entering the half-random gate, then there's a 0.427/(0.427 + 0.073) ≈ 85% chance that the first qubit is a 1. This is also what we would expect if the first qubit really was a 1 before entering the half-random gate. So no interference at all.

I claim that this is analogous to the elimination of the interference pattern in the original double-slit experiment when experimenters were able to sneakily detect which slit a photon went through, without disturbing the photon.. too much. Note that we don't actually need to open the second qubit in order for the interference to go away. The fact that we could open it is enough.

Philosophy of Observation

This business of "observation" in quantum mechanics is a bit of a contentious issue. I keep saying we "open" a qubit to see what's inside, and this action causes the qubit to become either definitely 0 or definitely 1, destroying whatever strange probabilistic state it was in before.

But, it seems like quantum mechanics is the model of how everything works. And we, as experimenters, are also part of everything. Which suggests that we are just qubits, in the same quantum system as our experiments. So how can we "open" the qubits in our experiment? That would be like part of a quantum computer opening the qubit of another part of the quantum computer. But this can't happen, because opening a qubit is destructive — it changes the state of a qubit to be exactly 0 or 1, forgetting what it could have been — and we believe quantum computation is reversible, so destruction is not possible.

I think the answer lies in the simple quantum computer we built above. The copy gate (which is not destructive, since it only copies if the second qubit is 0, so we know if both qubits are the same afterwards that the original second qubit was a 0) entangles one qubit with another. This entanglement is "observation" in the quantum sense. That is, if we think we're observing the contents of a qubit, what's really happening is that the qubits in our brain have become entangled with the qubit, and the giant state vector of the universe has some analog of the state [sqrt(.5), 0, 0, sqrt(.5)] where there's a 50% chance that the qubit was a 0 and our brain believes it was a 0, and a 50% chance that the qubit was a 1 and our brain believes it was a 1, and both of these states exist as far as the quantum universe is concerned. It's just that we as humans can't see the whole state vector of the universe. We can only "see" the state that represents a human believing it can see a particular state. I think that is what is meant by the many-world interpretation, but I'm not sure.