The Turing Machine

Artists rendition of a turing machine
Artist’s representation of a Turing machine. (Source: Wikipedia)

This is the sixth part in my multi-part series on computing. In the previous parts, we learned about Boolean logic, the language computers think in. We then learned how to implement this logic electronically. And finally, we learned how to make computer memory, so that computers can record results of calculations.

Now before we conclude the series, we’re going to take a quick detour into computational theory and the Turing machine.

Alan Turing’s Machine of the Mind

In 1936, mathematician, WWII codebreaker, and all around awesome guy Alan Turing wanted to investigate a problem in formal logic. Specifically, he wanted to find the answer to a question first posed by David Hilbert. Simplistically, the problem is this:

We know from Godel’s incompleteness theorems that some mathematical questions simply do not have answers. But Godel opens up a Hydra’s den. Are there some mathematical questions that have answers… but answers… but answers that it is impossible for a human being or machine to discover, even in principle?

To answer this question, Turing devised a theoretical machine designed to compute the answer to any question one can pose in mathematics. You’ve probably heard of it, even if you don’t know what it does. This is the Turing machine.

To Build a Turing Machine

A Turing machine is a pretty simple device, but it sounds complicated when you describe it. So I think the best way to understand what’s going on is by example. So let’s try a little experiment where we play the role of the “brains” of a Turing machine. I’m going to give you three things and you’re going to manipulate them to form a Turing machine.

First, I’m giving you a tape, say a long ribbon of paper, partitioned into little blocks or cells. With nothing written on it, it looks something like this:

The ticker tape in a Turing machine
The ticker tape in a Turing machine

(In principle the tape could be infinitely long, but we’ll ignore that.)

Initially, the tape WILL have some symbols written on it. It’ll look like this:

The ticker tape I give you.
The ticker tape I give you.

But let’s say I wrote on the tape in pencil. This means you can erase any symbol I’ve written on it and replace it with something else. Just make sure you use pencil!

I’m only going to allow you to write one symbol in each of the cells on the tape. And I’m going to restrict what you can write. Here are the symbols you can use: “1″, ” “, “-”,  and “=”, where ” ” represents a blank space.

Next I’m going to give you a spinner like the one you might get for a game of Twister. Ours will have an arrow that can point at one of four colors: Red (R), Green (G), Blue (B), and Yellow (Y).

You won’t just randomly spin the arrow. You’ll move the arrow to keep track of a color. Let’s start the spinner pointing to red, as shown below.

the spinner I give you
The spinner I give you. Let’s start it pointing to “red.”

Finally, I give you the following table. The table tells you what to do based on the symbol you read on the tape and the color of the spinner. Here’s the table:

The instruction set you have to use.
The instruction set you have to use.

Let’s work through it.

Now, just start by looking at the symbol in the leftmost cell of the tape, as shown below.

The starting state for our Turing machine.
The starting state for our Turing machine.

The symbol is a “1″ and the spinner is pointing to “Red.” If you look at your table, you see it tells you to do nothing and just look at the symbol in the cell one to the right. If you do, you see that this symbol is also a “1″ and we’re just supposed to move right again.

This process repeats for a while. The instruction table doesn’t tell us to do anything different until we reach the “=” sign shown below.

Where our Turing machine is when things start to get interesting.
Where our Turing machine is when things start to get interesting.

If we look at our instruction set, it tells us to “erase the symbol and replace it with a space” and then “move one cell to the left and change the spinner to point to Blue.” So let’s do that. After we do, the Turing machine looks like this.

Our turing machine after we erase the "=" sign.
Our turing machine after we erase the “=” sign.

Now the rules tell us to replace this symbol with an “=” sign, move one cell to the left, and change our spinner to point to “Green.” Let’s do that. The results are shown below.

Our Turing machine after we erase the "1."
Our Turing machine after we erase the “1.”

Now the rules tell us to move once cell to the left and change the spinner to “Yellow.”T he results are shown below.

Our Turing machine now that we've moved left past the "-" sign.
Our Turing machine now that we’ve moved left past the “-” sign.

Now the rules tell us to erase the “1″, replace it with a blank space, move to the right, and change the spinner to red, as shown below.

Our Turing machine now that we've changed our state back to "Red."
Our Turing machine now that we’ve changed our state back to “Red.”

Well, we know what to do when the spinner points to “Red.” We move right! This continues until we get to the equals sign, as shown below.

Our Turing machine after we reach the equals sign for a second time.
Our Turing machine after we reach the equals sign for a second time.

And we erase the equals sign, as shown below…

Our Turing machine after we erase the equals sign for the second time.
Our Turing machine after we erase the equals sign for the second time.

But now our spinner is pointing to “Green” and we’re looking at a “-” sign. The instructions tell us we’re done!

 So… What?

So what have we done, exactly? Well, our tape started with an expression that looked roughly like

    \[111 - 1 =\]

and we ended up with an expression that looked roughly like

    \[11 -\]

In other words, we used a simple tally mark system to take the number “3″ and subtract “1!” This sounds simplistic, but it’s not. We wrote down a set of rules so that given any number of tallies left of the equals sign and any number of tallies right of the equals sign, we can subtract the tallies on the right from the tallies on the left. And we can do so without any thinking at all, just by looking at the rules in our table.

So What’s a Turing Machine?

A Turing machine is only a little bit more general than what we just described. It has three parts:

  1. A ticker tape consisting of cells that can be written in. We select an alphabet of symbols we’re allowed to write. In our simplistic example, our alphabet consisted of “1″, ” “, “-”, and “=” but it could easily describe more symbols. For example, you could easily use the real alphabet or every character available in unicode. Whatever you like.
  2. A “head” that can read from the tape and write to it. The head also has a finite number of “states” or modes. You can think of these the same way you think of the modes available to your printer at home. A printer probably has a “scan” mode, a “print” mode, and mavbe a “fax” mode. These determine what the printer does given some input. Similarly, the state of the head determines what it does when it reads a symbol. In our example, the states were the four colors: “Red,” “Green,” “Blue,” and “Yellow.”
  3. A rules table. The table tells the head what to do when it reads a symbol off of the tape given the state it’s currently in.

Turing postulated that if there is a problem in mathematics that you can find the answer to, you can build a Turing machine that can find the answer. We currently believe this to be true, though the answer isn’t really known. (Aside: this hypothesis is called the Church-Turing Thesis.)

But, more relevantly (for us anyway), a Turing machine is a model of a single-purpose computer. Next time I’ll explain how and explain how to get from this to a fully programmable computer.

Further Reading

Here are some resources on Turing machines.

  • The Wikipedia article on Turing machines is, of course, a good place to start.
  • Mark C. Chu-Carroll has a very nice introductory article on Turing machines, from which I stole my example machine. You can find it here.
  • I-Programmer also has a nice article on Turing machines. It’s clearly meant for programmers and software engineers, but a layperson should be able to follow it. Find it here.
  • You can download a Turing machine emulator for your android phone here.
  • Want to learn how to build a Turing machine with a Raspberry Pi? Learn how here.
  • Google made a doodle Turing machine for Turing’s birthday. It’s archived here.
  • Want to build a Turing machine out of legos? You can! Find out more here.

Related Reading

This is the sixth article in a multi-part series on computing. These are the other parts:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.
  • In this article, I show how to use triodes to make logic gates.
  • In this article, I explain how to build computer memory.

Posted in Computer Related, logic, Mathematics, Science And Math | Tagged , , , , , | Leave a comment

A Parallel Computing Primer

Janus
The Janus Supercomputer at the University of Colorado is one example of a parallel computer.

So, Jonah is moving and he asked me to write a guest post. Jonah’s recent articles about computing prompted me to write about distributed computing. The question I will answer is: how do you go from computing with a sequential program to computing on many core machines (aka Parallel Computation)?

Parallel Computation

First of all, what is parallel computation? In a nutshell, parallel computation is the science which allows you to use a many processors to compute faster. You certainly would want to do this if you worked on the stock market where the faster you are at calculating the faster you can buy and sell and make money. If you are trying render a TV show you’ll want to finish it before it is supposed to air. Many newer computers have many processors in them allowing them to take advantage of this speedup gained from using them.

I now want to discuss what it means to have a sequential program, which is the case when only one processor is used. To solve most problems you have a sequence of steps you must complete to get an answer. For example, suppose you want to find the sum of the numbers:
1 2 3 4 5 6 7 8

Computers can only do binary addition, that is add two numbers at the same time. Because of this we must add only two numbers at a time. Two possible ways are outlined below:

(((((((1 + 2) + 3) + 4) + 5) + 6) +7) +8) +9
or like this
((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8))

The second way might not seem obvious but it lends itself to parallelization so we’ll use it as our primary example. Since we are only adding pairs of numbers we can give each pair a letter to represent it. So, in this case A represents the action of adding 1 and 2 and B represents adding 3 and 4, and so on. It’s a bit more abstract but E equals the sum of the results from A and B and similarly for F and G.

((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8)) = ((A + B) + (C + D)) = (E + F) = (G)

To exemplify the sequential case: suppose you have a single processor which can only do one operation at a time. It would look like a single channel which you could send commands to which would be operated on sequentially.
====================================
CPU 0 | A B C D E F G
====================================

This is called the sequential method where only one processor is utilized.  If each step took 1 second to complete, this code would take 7 seconds. The steps could be performed in other orders as long as A and B come before E, C and D before F, and E and F before G. If this wasn’t the case, you wouldn’t have the output from the steps before and the code wouldn’t work.

Now, the trouble occurs when you have two processors. How do you decide how to run the commands in parallel? This example is pretty straight forward, you can only use commands that have left and right answers available for them. Using the example above, an efficient order could be
=====================================
CPU0 | A | B | E | G
=====================================
CPU1 |  C | D | F |
=====================================

Here A and C, B and D, and E and F are all performed in parallel. We can’t parallelize G as it just adds the two last numbers together and that can only be run on one processor. Now, again if each operation only takes one second then this would take 4 seconds. We seemed to have achieved a 3 second speed up in our code.

Flynn’s Taxonomy

Our example before this outlines one of the most common ways to run a program in parallel. However, there are many way to do multi-processing. To help identify the different types Michael J. Flynn created a taxonomy. His taxonomy, simply called Flynn’s Taxonomy, splits all programs into four groups denoted by SISD, MISD, SIMD, MIMD. You can visualize the taxonomy in the following graphic:

Flynn's Taxonomy
Flynn’s Taxonomy (By Wikipedia’s User:Cburnett)

The four types are separated into if they have one or more of each an instruction set and data set. The four combinations yield the four types in Flynn’s Taxonomy.

The four types with their names expanded are as follows:

  1. SISD – Single Instruction Single Data
  2. MISD – Multiple Instruction Single Data
  3. SIMD – Single Instruction Multiple Data
  4. MIMD – Multiple Instruction Multiple Data

The sequential addition code is an example of the SISD type, and our parallel addition example is illustrative of the SIMD (Single Instruction Multiple Data) type. This is because each processor does the same thing, take four numbers and add them pairwise. However, CPU0 gets the numbers 1 2 3 4 and CPU1 gets 5 6 7 8. This means each set of instructions get a unique set of inputs.

So, you might ask, how do the other two types come into play. Well the MISD case can be an instance when say you have medical records of many patients, and you want to know if your model (A) predicts cancer better than another model (B). You would want to check it on the same data but you want to run two different instructions or models; in this case A and B.

As for MIMD, this usually comes about when processing large amounts of different data. For example, suppose you are Google and you have billions of photographs. If you want to store them in the most compact form possible you’ll probably want to compress them. Since different photos lend themselves to different compression algorithms you might want to compress it with two different algorithms (the instructions) and keep the best one. I’m not saying this is how they do it but it does illustrate an instance where you might use a MIMD type program.

An Example of Parallel Code

Weather simulations need to be fast and accurate. To accomplish the accuracy, software divides the surface of the earth up into little squares. Each square represents the whole area and contains the data for its temperature, humidity, wind, etc. To make the simulation doable the whole area is represented as a single point usually located in the center of the region.

To simulate the weather, the program will move air from such one point to another to represent wind. The wind carries water and clouds which change the temperature and, not to make it sound too simple, changes the weather. By simulating this we can predict to a reasonable extent how the weather will unfold tomorrow.

Of course, if the region is too large it will not reflect the weather accurately. For instance, if the region was chosen to be the size of the US, it would represent all the weather in the US as the same, which certainly isn’t true. The size of a region is usually about the size of a large neighborhood as seen below:

A NWS prediction area
A prediction area for south Boulder. (Credit: NWS www.weather.gov)

There is a cost to choosing a small area, you need more memory to store all the information for all of the regions. Additionally, each time you add more regions you must do computations on those new regions increasing the computing time.

To overcome this, the National Weather Society (NWS) predictions weather on large distributed computer systems putting a few areas onto each computer. Then each computer applies the same instructions to each set of areas progressing the simulation one small amount of time into the future. This is then done many times until the future time is reached.

This way they can have predictions about tomorrow’s weather before tomorrow gets here.

The Trouble With Parallelized Programs

At this point it might seems as if we could continue to use more computers and get better and better performance. This would be nice but we run into the issue that not all code is parallelizable. Remember the sum of numbers problem, the last step required us to use only one processor to add the two final numbers together. In fact if we add more processors to that example we see more steps that can only be run sequentially.

=====================================
CPU0 | A | E | G
=====================================
CPU1 |  B | F |
=====================================
CPU2 | C |
=====================================
CPU4 |  D |
=====================================

Here, if we assume each step takes a second, we use 3 seconds. This means when we have 1 processor it took 7 seconds, with 2 it took 4 seconds, and with 4 it took 3 seconds. It seems as we add more processors we get a diminishing return in speedup. In fact if we add more than four there will be no additional speedup. This fact is called Amdahl’s Law.

"AmdahlsLaw" by Daniels220 at English Wikipedia - Own work based on: File:AmdahlsLaw.png. Licensed under Creative Commons Attribution-Share Alike 3.0 via Wikimedia Commons - https://commons.wikimedia.org/wiki/File:AmdahlsLaw.svg#mediaviewer/File:AmdahlsLaw.svg
Amdahl’s Law showing potential speedup for different parallel portions. (Daniels220 at Wikipedia)

Amdahl’s Law gives us a set of equations which depend of the portion of the code that is parallelizable and number of processors used. The graphic above shows us that for any proportion of parallelizable code, there is an upper limit to the speedup. Past a certain point, it is not possible to get more speed by adding more processors.

This fact has forced people to look for alternative methods to speedup their code. Most of the time they find better algorithms and mathematics which simplify what they must do to solve a problem and this make it run faster.

Conclusion

Parallel computing makes it possible to do large calculations in a timely manner but it is not a simple situation and there are certainly caveats to be aware of. But as computers become more parallel (which is a discussion for another day), parallel computing becomes a bigger and bigger deal. For example, Google recently created a  system for processing big data in an efficient way called MapReduce.

Jonah uses very parallel computers to study gravitational physics and he’ll discuss the intricacies of scientific computing in this environment sometime soon.

Hope this inspired some of you to investigate further. Feel free to ask any questions you might have.

Posted in Computer Related, Science And Math | Tagged , , , , | 1 Comment

Moving (again)

Cute moving dog
Cute moving dog

For (hopefully) the last time in the next three years, I’m moving! It’s only one city over, but I want to try and keep up a semblance of work productivity while I pack up and hop. So for the next two weeks or so, the blog will be on hiatus. Sorry all!

 

I will try to put up some fun content sporadically. And hopefully a guest post.

Posted in Uncategorized | Leave a comment

Flip-Flops and the Art of Computer Memory

It’s a poor sort of memory that only works backwards.
~The White Queen to Alice
(Lewis Carroll, Through the Looking Glass)

Keyboard Flip-Flop
It may surprise you to learn that flip-flops are an integral part of computing. Just… not the kind of flip-flop you think. (source)

This is the fifth part in my multi-part series on how computers work. Computers are thinking machines, and the first four parts of my series have been on how we teach computers to think.  But all of this logic, electronic or otherwise, is useless unless our computers can remember what they did. After logicking something out, a computer needs to remember the result of all that logicking!

In this post, I describe how to use the logic gates described in part four to electronically implement computer memory.

This post depends heavily on my last few posts, so if you haven’t read them, you might want to.

Still here? Okay. Let’s get to it!

 How Computer Memory Should Work

Before we talk about exactly how we implement computer memory, let’s talk about what we want out of it.

In the world of Boolean logic, there is only true and false. So all we need to do is record whether the result of a calculation was either true or false. As we learned in part three, we represent true and false (called truth values) using the voltage in an electric circuit. If the voltage at the output is above +5 volts, the output is true. If it’s below +5 volts, the output is false.

So, to record whether an output was true or false, we need to make a circuit whose output can be toggled between + 5 volts and, say, 0 volts.

Logic Gate, Logic Gate

To implement this, we’ll use the logic gates we discussed in part four. Specifically, we need an electronic logic gate that implements the nor operation discussed in part two. A nor B, which is the same as not (A or B), is true if and only if neither A nor B is true. We could use other logic gates, but this one will do nicely.

As a reminder, let’s write out the truth table for the logical operations or and nor. That way, we’ll be ready to use them when we need them. Given a pair of inputs, A and B, the truth table tells us what the output will be. Each row corresponds to a given pair of inputs. The right two columns give the outputs for or and nor = not or, respectively. Here’s the table:

truth table for OR and NOR
The truth table for the logical operations “A OR B” and “A NOR B.” Each row corresponds to a different set of inputs A and B; the last two columns correspond to the appropriate outputs.

Let’s introduce a circuit symbol for the nor gate. This will be helpful when we actually draw a diagram of how to construct computer memory. Here’s the symbol we’ll use:

a nor gate
A symbol for a NOR gate. The two terminals on the left correspond to the inputs. The terminal on the right corresponds to the outputs.

Crossing the Streams

Okay, so how do we make computer memory out of this? Well, we take two nor gates, and we cross the streams…

Ghostbusters crossing the streams
Don’t cross the streams. You know, unless you have to. (Source)

We define two input variables, which we call S (standing for set) and R (standing for reset), and two output variables, which we call Q and not Q. The reasons for this peculiar naming scheme will become clear in a moment. Then we wire the output of each of our nor gates so that it feeds back into the other nor gate as an input, as shown below.

An SR latch
One kind of computer memory constructed by cross-wiring two NOR gates. We have two input variables, called S and R, and two output variables, called Q and not Q.

For reasons that will eventually become clear, this circuit is called an SR-Latch, and it’s part of a class of circuits called flip-flops. Now let’s see if we can figure out what’s going on. Assume that both S and R are false for now. And let’s assume that Q is true and not Q is (as the name suggests) false, as shown below. 

SR latch Q state
An SR latch such that the Q state is true, the NOT Q state is false, and both S and R are false. This state is self-perpetuating. Blue indicates FALSE. Red indicates TRUE.

Is this consistent with the truth table we listed above?

  • S nor Q is false, because if Q is true, then (obviously) both S and Q aren’t false. Since we gave the name “not Q” to the output of S nor Q, this means not Q must be false. That’s what we expected. Good.
  • R nor (not Q) is true, because R is false and not Q is false. The output of R nor (not Q) is the same as Q, so Q must be true. Also what we expected!

Okay, so what does this mean? It means that if we start our circuit in this state, with R and S as false, Q as true, and not Q as false, our circuit perpetuates itself in this state. Nothing changes.

Toggle Me This, Toggle Me That

Now let’s alter the state described above a little bit. Let’s change R to true. Since R is true, this changes the output of R nor (not Q) to false. So now Q is false…and since S is still false, the output of S nor Q is now true. Now our circuit looks like this:

SR_latch_not_Q_toggle
An SR latch mid-toggle. We set R to true. Immediately, Q becomes false, which causes NOT Q to become true.

And if we wait a moment further, the cross-wiring takes effect so that both inputs to R nor (not Q) are true. This doesn’t change the output, though, as shown below.

SR_latch_not_Q_toggle_2
An SR-latch mid-toggle. After NOT Q becomes true, it feeds back into the first NOR gate. Fortunately, this doesn’t seem to affect anything.

Now we can set R to false again, and Q will stay false and not Q will stay true, as shown below.

SR_latch_not_Q
An SR-latch with Q false and NOT Q true. We got to this self-sustaining state by temporarily setting R to true.

Look familiar? This is the mirror image of the state we started with! And it’s self-sustaining, just like the initial state was. With both R and S set to false, not Q will stay true as long as we like.

Although R is false now, the circuit remembers that we set it to true before! It’s not hard to convince ourselves that if we set S to first true and then false, the circuit will revert to its original configuration. This is why the circuit is called a flip-flop. It flip-flops between the two states. Here’s a nice animation of the process I stole from Wikipedia:

SR latch animation
An animation of the flip-flop process for the NOR-gate based SR-latch we talked about. In this animation, RED signifies TRUE and BLACK signifies FALSE. (source)

This is computer memory. And similar devices are behind your CPU cache and other components inside your laptop.

A Whole World of Flip-Flops

Although it’s technically correct, generally, people don’t refer to the circuit I described as a flip-flop. The things people usually refer to as flip-flops usually only change state based on some sort of timer or clock. However, the idea is essentially the same.

In general, clocks are something I didn’t touch on. Real computers use a clock to sync the flipping of memory with the computations they perform using the logic gates I talked about earlier. (Clocks can also be generated using logic gates. This is the speed of your CPU clock.) I figured I wouldn’t go into that here because it’s a bit too technical and, in my opinion, not necessary for understanding.

Next Time

We now have enough tools to understand the essentials of how a computer works. It performs logical operations using logic gates, and it remembers what it did using flip-flops. Next time, we’ll take a break from electronic computers to discuss some other ways you can make a computer. Did you know you can make a computer with gears? With ropes and pulleys? With dominoes? With card games? Find out more next time.

Further Reading

Flip-flops are the domain of electrical engineers, so there’s not much non-technical material on them. Here’s what I could find.

  • A flip-flop is a special case of a class of circuits called “bi-stable vibrators.” If you like, you can learn about them on their Wikipedia page.
  • Here’s a fairly technical video lecture on flip-flops.
  • This set of lecture notes is at about the same level as my post, but it goes into substantially more depth.
  • If you want to understand clocked flip-flops, you might start here.

Related Reading

If you liked this article, you might enjoy reading my previous entries on computing:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.
  • In this article, I show how to use triodes to make logic gates.

If you like explanations of how hardware works, here are some similar articles:

Posted in Electronics, Physics, Science And Math | Tagged , , , , | Leave a comment

The Boolean Circuit and Electronic Logic, Part 2

If the presence of electricity
can be made visible
in any part of the circuit,
I see no reason why intelligence
may not be transmitted
instantaneously by electricity.

~Samuel Morse

Circuit Board Snake
This sculpture by Peter McFarlane embodies the fear a lot of us feel regarding the innards of a computer. If we touch it, it might bite! Have no fear. Today we learn what all those wires on that board do.

This is the fourth part in my multi-part series on how computers work. Computers are thinking machines, but they can’t do this on their own. We need to teach them how to think. And for this, we need a language of logic. In the first part of the series, I introduced this language of logic, Boolean algebra. In the second part, I described how to formulate complex logical statements using Boolean algebra. In the third part, I described how some of the electronics in old-school computers worked.

This time, I finally get to the meat of things. I describe how you can use the circuits described in part 3 to actually implement Boolean logic electronically.

Voltages

The following discussion is going to depend heavily on an understanding of the triode vacuum tubes that I discussed last time. So if you haven’t already, you probably want to last week’s article before you read this one.

That said, some review is probably in order. First let’s review electric voltage. The salient points are this. Electrons want to flow from places in a circuit that are at low voltage to places that are at high voltage.  Voltage is measured in volts. We want to use voltage as a stand-in for the truth values described in parts one and two of my series on how computers work.

There are a number of ways we can use voltage to represent truth values. But let’s pick the most common way. Let’s say we have a circuit. We’ll connect a voltage-measuring device to a spot on our circuit—perhaps where two wires intersect—and say that, if it reads any voltage higher than +5 volts, then our circuit represents true at that spot. If it reads any lower, then our circuit represents false there.

(There’s an important detail I’m skipping here. Voltages are not absolute numbers. We know that electrons flow from low voltage to high voltage. But we need a baseline for what “zero volts” means. In every circuit, this “zero volts” value might be different, but we always have to set it and choose a value. We usually call “zero volts” ground.)

Vacuum Review

 Now let’s review the basics of a triode. As the name suggests, a triode is a circuit component with three terminals, called the cathode, anode, and filament, as shown below. There’s another piece called the called the heating element that we won’t discuss in much detail.

triode schematic 1
A schematic of a triode.

I discuss the triode in great detail in last week’s article.  But for now, here’s what you need to know. The filament controls the flow of electrons from the cathode to the anode. Suppose that I hook up the triode in a circuit so that the anode is at a high voltage, and the cathode is at a low voltage. Then if the filament is at a low voltage like the cathode, then no current will flow. If the filament is at a high voltage like the anode, then current will flow.

Fiddly Names

It’s worth noting that the pieces of a triode can have other names. The cathode is often called the plate and the filament is often called the grid. In this naming scheme, confusingly, the heating element is often called the filament.

It’s also worth noting that these days triodes have been almost completely replaced by transistors.But transistors have different names for these parts. In a transistor, the cathode is called the source, the anode is called the drain, and the filament (or grid) is called the gate. A transistor does not have a heating element. To avoid confusion, I’ll use vacuum tubes instead of transistors. And I’ll use the names in my diagram.

Boolean Circuity

Now let’s implement Boolean logic! To do this, let’s chain some triodes together, as shown below.

an or gate implemented using vacuum tubes
An or gate made out of triodes. We keep the anodes at a very high voltage, much higher than the cathodes could possibly be at. Then we connect both cathodes to a terminal that we call “C.” We name the filament terminals “A” and “B” respectively.

Here we keep the anodes at a very high voltage, much higher than the cathodes could possibly be at. We then connect both cathodes to a terminal that we call C. We name the filament terminals A and B respectively.

Now let’s manipulate the terminals A and B and see what terminal C does.If both A and B are at a low voltage (i.e., false), then current won’t flow through either triode. The result is that C stays at a low voltage, which we’ll call false. But now let’s put terminal A at a higher voltage, say true. (For now we’ll leave B as false.) Then current will flow through the left-most triode and raise the voltage at terminal C so that it becomes true. 

Similarly, if we keep A at a low voltage (i.e., false) but raise the voltage at B so that it becomes true, then current will flow through the right-most triode. This too will raise the voltage at terminal C and make it true. And of course, if both A and B are true, then current will flow and raise the voltage at C, making it true.

So if both A and B are false, then C is false.But if either A or B or both A and B are true, then C is true too. The astute among you might recognize C as the result of the logical operation A or B. We’ve just made the logical or work electronically! The circuit we just constructed is called an or gate.

More Gates

Can we do the same thing to make a logical and? Let’s try. We’ll still use two triodes. But now let’s connect them in a different way, as shown below. We put the anode of the first triode at a very high voltage. But we connect its cathode to the anode of the second triode. We label the filaments A and B respectively and the cathode of the second triode C.

An and gate implemented with triodes.
An and gate implemented with triodes. We keep the anode of one triode at a very high voltage. But we connect the cathode to the anode of a second triode. We call the filament terminals “A” and “B” respectively and the cathode of the second triode “C.”

Now current will be unable to flow unless both terminals A and B are at a high voltage. In other words, C will be true only if both A and B are true. You might then recognize C as the output of the logical A and B, which we’ve now implemented electronically! This circuit is called an and gate.

Gates in Practice

I showed you how to electronically implement the boolean operations and and or described in George Boole and the Language of Logic, Part 1. If we wanted to make composite statements as we did in part 2, then we’d also need the not operator. But that’s actually a bit trickier (though not impossible) to make electronically. So I won’t describe it.

Usually, in practice, people use nand and nor gates as opposed to and, or, and not. These are harder to make, however, so I won’t describe them. Hopefully the gates I did describe, however, give you a feel for how this works.

Electronic Caveats

In my description of the and and or gates, I claimed that when current flowed through a triode, the voltage at the cathode changed. In practice things are a lot more complicated. Voltage and current are related. In simple cases, the relationship is given by Ohm’s law, which many of you are probably familiar with. In more complicated cases, where the current changes quickly, you need to take more things into account, like the travel time of electrical signals.

That said, the description I gave gets the basic idea across and, if we added more circuit components (such as, capacitors, inductors, and resistors), the gates I described would work.

Next Time

Performing a logical calculation is useless unless you can record your findings. Next time, I’ll describe how to use logic gates to teach computers how to remember.

Further Reading

If you want to know more, here are some resources on how logic gates are implemented.

Related Reading

If you liked this article, you might also like the following articles I’ve written.

I am currently in the middle of a series on how computers work, from the ground up. Here are the previous articles:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.

And if you like articles on how things work. Here are some other articles I’ve written in the same vein.

Posted in Computer Related, Electronics, logic, Mathematics, Physics, Science And Math | Tagged , , , , , | 1 Comment

The Boolean Circuit and Electronic Logic, Part 1

Living in a vacuum sucks.
~Adrienne E. Gusoff

circuit paleontology
As this sculpture by Peter McFarlane indicates, today we are circuit paleontologists. We look into the past history of circuitry to learn about modern computers.

This is the third part in my multi-part series on how computers work. Computers are thinking machines, but they can’t do this on their own. We need to teach them how to think. And for this, we need a language of logic. In the first part of the series, I introduced this language of logic, Boolean algebra. In the second part, I described how to formulate complex logical statements using Boolean algebra.

Now, in part three, I lay the groundwork for how we can implement simple Boolean logic using electronics. In this part, I describe the old-school electronics that people used for the first electronic computers.

Circuit Basics

Before we talk about logic in electronics, let’s take a moment to quickly discuss electronics as a whole. An electric circuit drives and takes advantage of the motion of electric charge. There are two flavors of electric charge, positive and negative. As the old adage goes, opposites attract and like-charges repel. So two positive (or negative) charges are repelled from each other, while a negative charge is attracted to a positive charge.

There are two important quantities we need to think about: current and voltage. Current describes the number of charges passing through a given piece of metal, like a wire, per second. If we imagine that charges make up a fluid like water, then electric current is exactly analogous to speed of the flow of the liquid. We measure current in amperes, or amps, after Andre-Marie Ampere.

Voltage is current’s desire to flow. In science lingo, it’s the potential energy per unit of charge at a given point in space. This is hard to visualize, so let’s talk concretely. If I have several positive charges near each other, they all repel and they want to move away from that point. So this is a place of high voltage. Voltage is always described in terms of positive charges. So if I have several negative charges next to each other, then even though the negative charges are repelling each other, a positive would just love to get near that negative action and it will go towards the spot. This is a place of low voltage.

We can generate voltage in a number of ways. But the one you’re probably familiar with is a battery. The positive terminal on a battery is a place of high voltage and the negative terminal is a place of low voltage.

We all know that water flows downhill. So in our water analogy, voltage is the height of the water. High voltage is a hill and low voltage is a valley. Positive charges like to flow from hills to valleys. But if a positive charge is already sitting in a valley, it’s probably not going anywhere. (If you like, you could instead think of it as the pressure of the water.) We measure voltage in volts, after Alessandro Volta.

In physical electric circuits, electrons, which have negative charge, are the charges moving through the circuit. By convention, current is defined in terms of positive charge, so current flows in the opposite direction that the electrons are moving. And similarly, electrons travel from low voltage to high voltage. Electrons flow uphill.

The Voltage of Truth

If we want to use electronics to implement Boolean logic, we need something to represent the values true and false. There are a number of choices, but a common one is to use voltage. Let’s say we have a circuit. We’ll connect a voltage-measuring device to a spot on our circuit—perhaps where two wires intersect—and say that, if it reads any voltage higher than +5 volts, then our circuit represents true at that spot. If it reads any lower, then our circuit represents false there.

But how can we control voltage? Well, fortunately, it’s just how attracted a positive charge is to a given area. In other words, it’s the density of electrons! (Or the density of protons if the positive charge is repelled from a region.) For example, (very roughly) electrons can move completely freely inside conductive metal like copper. So, since electrons repel each other, they will tend to distribute themselves evenly along a wire. This means that the wire will be at the same voltage all along its length.

Electrically Powered Electric Switches

So to control voltage, we just have to control the number of charges. How do we do that? Well, one way is a mechanical wall switch. If you flip a wall switch, you’ve probably closed a circuit allowing current to flow, adding charge, and changing a voltage. But this isn’t terribly useful for us because it requires us to take action. We want our circuit to behave like a Boolean truth table. The output voltage (or truth value) should depend on the input voltage(s).

The trick is that we place the burden of flipping the switch onto the electronics. In the olden days, we used a specific type of vacuum tube, called a triode, shown below. It’s called a vacuum tube because there’s no air inside the glass. It’s called a triode because there are thee terminals that you connect to when you make a circuit.

triode
A classic example of a triode. The anode and the cathode are the terminals on the right of the image. The filament terminal is at the top. (source)

Here’s what it looks like inside:

triode schematic 1
A schematic of a triode.

The three terminals are called the cathode, the anode, and the filament respectively. The cathode and anode are connected to metal plates, while the filament is connected to a a wire mesh that electrons can pass through. Near the cathode, there’s a heating element which heats the cathode up.

Let’s ignore the filament for a moment. If we put the cathode at a low voltage and the anode at a high voltage, the heating element heats up the cathode, and boils electrons off of it. They’re then attracted by the anode and they fly to it. So an electric current flows from the anode to the cathode, as shown below. (Remember current flows in the direction opposite to the direction the electrons travel.) Since electrons are traveling into the anode, this might change the voltage from high to low.

triode schematic 2
Suppose we apply a high voltage to the anode, a low voltage to the cathode, and no voltage at all to the filament. Then the heating element boils electrons off of the cathode. They’re attracted to the anode and they fly to it, so a current flows.

But now let’s say we put the filament at a low voltage too. It repels the electrons. So now after we boil them off of the filament, they won’t want to travel. This means that if we put the filament at a low enough voltage we can stop the flow of current completely, as shown below.

triode schematic 3
If we put the filament at a negative voltage just like the cathode, then no current flows.

In other words, we can control the current between the anode and the cathode by using the filament!

Naming Conventions

+Hamilton Carter at Copasetic Flow (who both uses Ham radios and used to design microchips and knows much more about the innards of computers than I)  pointed out that there’s another common nomenclature for the terminals on a triode. The terminal I labeled the anode is often called the plate and the terminal I labeled the “filament” is often labeled the grid. This is important because then people call the heating element that boils off electrons a filament.

Sorry. It’s confusing, I know. Anyway, thanks Hamilton!

(By the way, if you haven’t already, you should check out Hamilton’s blog, Copasetic Flow. Like me, he’s a physicist in training and he posts some awesome stuff.)

Wishy-Washy Wibbly Wobbly Electronics


I feel the need to warn you that I’ve taken a _lot_ of liberties with my explanation of how the electronics work, especially in my electronics basics section. I wanted to say just enough so that you could understand the implementation of Boolean logic, which comes next time.

The biggest liberty I’ve taken is with the relationship between current and voltage. In simple circuits, there’s a simple relationship based on the resistivity of the wire, called Ohm’s Law. But in circuits where currents are changing very quickly, the relationship is much more complicated.

Perhaps at some point I’ll do a post on this.

 Along Came the Transistor

Nowadays of course, no one uses triode vacuum tubes. Instead we use transistors, which are made using quantum mechanics, nanofabrication, and badass science wizardry. I’m not discussing transistors here because they’re a bit complicated and I didn’t want to muddy the discussion. The triode gets the idea across, and it’s a neat bit of computer history.

That said, transistors are dramatically better than vacuum tubes in basically every way. They’re millions, possibly billions, of times smaller and cheaper to produce. And they react to electrical signals much much faster. The only disadvantage is that transistors aren’t as durable as vacuum tubes and they can’t handle voltages nearly as high.

I wrote about transistors a while back. If you’re interested I suggest you check out the following articles in order:

William Beaty also has a beautiful and simple article on how a different type of transistor, the bipolar junction transistor, works. Check it out here.

Further Reading

Still curious about vacuum tubes? Here are some resources:

Next Time…

Now that I’ve introduced vacuum tubes, I’ll use them next time to finally explain how to implement Boolean logic electronically. See you then!

Posted in Computer Related, Condensed Matter, History, logic, Mathematics, Physics, Science And Math | Tagged , , , , , , , , | 7 Comments

George Boole and the Language of Logic, Part 2

Anything that thinks logically
can be fooled by something else
that thinks at least as logically as it does.

~Douglas Adams

George Boole V George Boole
Without the work of George Boole, we wouldn’t have binary logic and we would be unable to teach modern computers anything. (Original image from Wikipedia. Modifications with jp2a and gimp script-fu.)

This is the second post in a multi-part series explaining how computers work. A computer is a thinking machine, a device which applies logic to any problem we ask it to. However, computers don’t know how to do this automatically. We have to teach them. And to teach them, we need a language of logic.

Last time, we introduced one such language of logic, Boolean algebra. This time, we learn how to make composite statements in Boole’s system.

This post will depend heavily on the preceding one, so if you didn’t read last week’s post, check it out here.

Let’s pick up where we left off. We’d just written out the truth tables for not, and, or, and if-then.

More Complex Statements

We can use the truth tables we’ve written out to construct statements of arbitrary complexity. All we have to do is combine them!

For example, we noticed earlier that the truth table for the word or is a bit outside of the colloquial use. The reason was that if both statements A and B are true, then the statement A or B is also true. It would be much more intuitive if the statement A or B was true if A was true or B was true, but false if both A and B were true. This would certainly describe a coin flip better!

The word for this operation is called xor, meaning exclusive or. Like and, or, not, and if-then, it has a truth table. We could simply define xor‘s truth table to have the properties we want, but instead, let’s try to get it by combining other truth tables.If we want to compute A xor B, we know we’ll need A or B and A and B—so let’s tabulate those first, all together in the same table:

xor 1
The setup for our derivation of the xor truth table.

All I’ve done for now is copied the truth tables for A and B and A or B onto a single table, then left some additional columns suggestively blank.

Since xor means we want one and only one input to be true–that is, we want either A or B to be true, but not both—let’s first write out what happens when we negate A and B. To do this, we look at its true/false values, found in the third column. On every row where we see a True in that column, we write a False in the fifth column (the first blank column). Likewise, every time we see a False in the third column, we write a True in the fifth column. The results are tabulated below. I added parentheses to Not (A and B) to emphasize that we’re negating the combined statement A and B, not just negating A.

xor 2
Our derivation of the xor truth table, continued.

We’re almost there! To finish, let’s calculate what (A or B) and (Not (A and B)) is, since that “compound operation” fully describes what we mean when we say xor. To do this, we use the and truth table from before. But instead of starting all the way back at the A and B columns, like we did before, we use the truth results we tabulated in the A or B and Not (A and B) columns of our new truth table:

xor_3
Our truth table for xor, fully calculated! It looks like A xor B is the same as (A or B) and not (A and B).

Let’s look at the last column. Now that looks like an intuitive “xor” statement! If A and B are both true, then the statement A xor B—which is the same as (A or B) and not (A and B)—is false. If either A or B is true and the other input is false, A xor B is true. And if both A and B are false, A xor B is false. Perfect!

It turns out that we only need not and and or or to construct any other composite statement. Even the if A then B causality statement we introduced before can be written as a combination of the more elementary words: if A, then B is the same as not (A and not B). Try it out for yourself and see!

Truth Arithmetic

Earlier, I mentioned that we often use the numbers 1 and 0 for the values true and false respectively. Let’s try that now. In fact, let’s take it one step further and assign some familiar symbols to the words and and xor. Let’s make and a multiplication sign (x) and xor a plus sign (+).

This allows us to write out statements as equations whose right-hand sides tell us the true/false value of their left-hand sides. For example, true xor false becomes 0 + 1, and since 0 + 1 = 1, this means that true xor false is true. For another example, we can write true and false as 0 x 1 = 0, or false. If we concede that 1 + 1 = 0, then we can do this arithmetic with every combination of true and false. We only have to remember that when we negate, we replace every zero with a one and every one with a zero.

This is why binary is famously written as ones and zeroes!

Logic and Mathematics

A lot has happened in mathematics since Boole first described his language of logic. Mathematicians have carefully rebuilt the entire field from the solid foundation of these simple logical ideas. It’s not an exaggeration to say that all of mathematics is an intricate application of this kind of logic.

The way I like to think about it, mathematics is a way for us to keep ourselves honest. It’s a careful set of rules and a language to go with them, made so that when we think carefully about something, we know we’ll get the right answer. And it all starts with Boolean logic.

…Well, sort of. It doesn’t have to be this way. Boole chose to use two values of truth: true and false. But mathematicians have since discovered that we can do just as well with three truth values: true, false, and sort of. Or infinite truth values ranging from completely true to completely false. Thinking in this way is much harder, of course, so most people don’t. But it is possible. If there is an alien counterpart to Boole on an alien world somewhere, maybe those aliens think in terms of “yes,” “no,” and “sort of.”

Next time I’ll explain how we implement Boole’s logic electronically to build a computer.

Related Reading

After my previous post, many people suggested some excellent resources. Here they are.

  • +Jean-Baptiste Queru has an absolutely wonderful post on how dizzyingly complicated computers are. You can find it here.
  • +Kevin Clift found this video of implementing logic with strings and pulleys.
  • Kevin Clift also found a textbook on Boolean Logic by Lewis Carroll, of Alice fame. You can find it here.
  • +Olafur Jens Sigurdsson pointed me to this absolutely amazing MIT course that walks the student through the creation of a simple computer, from the hardware to the operating system to the program.
  • Boolean logic is the topic of many first-year college computer science and mathematics courses around the world. If you’re interested in learning it at a deeper level, here’s an online course you can take.
  • A good place to start is Wikipedia’s page on Boolean logic.
  • Some math bloggers have attempted to describe Boolean logic with more depth. I particularly like professional math tutor John M.’s article. You can find it here.

You May Also Enjoy

If you liked this post, you might enjoy my other posts on mathematics:

Posted in logic, Mathematics, Science And Math | Tagged , , , , , , | 3 Comments

George Boole and the Language of Logic, Part 1

Logic takes care of itself;
all we have to do is to look
and see how it does it.

~Ludwig Wittgenstein

Contrariwise,
if it was so, it might be;
and if it were so, it would be;
but as it isn’t, it ain’t.
That’s logic.

~Lewis Carroll

George Boole in binary ascii
Without the work of George Boole, we wouldn’t have binary logic and we would be unable to teach modern computers anything. (Original image from Wikipedia. Modifications with jp2a and gimp script-fu.)

This is the first post in a multi-part series explaining how computers work. At its heart, a computer is a logical-thinking machine. It’s very good at starting with several assumptions and deducing a conclusion from those assumptions.

Of course, a computer can’t do any of that on its own. We need to teach it how to think first. And to teach it how to think, we need a language of logical thought. Fortunately, logic has a language we can use, first proposed by George Boole (pictured above) in his 1854 treatise An Investigation of the Laws of Thought. In his honor, this language is called Boolean Logic or Boolean Algebra.

Since the very construction of computers is based on this language of logic, our very first post will be on Boole’s laws of thought.

True and False. One and Zero.

George Boole was a mathematician who wanted his language to be as precise as mathematical law. He did away with fuzzy ideas like “kind of” and “maybe.” In Logic, Boole argued, every statement is either true or false. Something can’t be “kind of true,” “maybe true,” or “probably true.”

Suppose that I flip a coin without looking and say, “Maybe it landed on heads and maybe it landed on tails.” That statement may be technically true, but it’s too vague to communicate anything of value. The most correct—and true—statement, Boole would argue, is “the coin landed on heads or the coin landed on tails.” When talking about events like that, there’s no room for “maybe.”

Nowadays, we often use the number 1 to symbolize true and 0 to symbolize false. (Hence the name “binary logic.”) For reasons we will see, this is very convenient, especially in computers. But for now, as we introduce the topic, we’ll use T for true and F for false.

Note that I will be using the words “true” and “false” and the letters “A” and “B” a lot below. To make them stand out and make my paragraphs easier to read, I will be bolding important words and symbols. I’m not yelling at you or emphasizing those specific words. I’ll italicize for emphasis.

Tabulating The Truth

Intuitively, we know that if a statement is not true, it’s false. However, a computer doesn’t know that. It has no idea what words like “and,” “or,” or “not” mean… or what any words mean, for that matter. But we can teach it by defining things called truth tables. This will be easiest to explain by example, so let’s look at the truth table for and:

Truth table for "and"
The truth table for the word “and.”

Each column describes the value for a different statement. Statements A and B in the first two columns could be anything. Statement A might be “I have a dog” and statement B might be “I have a cat.” The third column is the statement A and B. So in our case, “I have a dog and I have a cat.”

Each row tells us the truth value of the statement in question. So, for example, if we look at the second row, if A is true and B is false, the statement A and B is false. To continue our pet example: The second row describes a situation in which I have a dog but not a cat. Note that, in order for the statement A and B (“I have a dog and I have a cat”) to be true, both statement A (“I have a dog”) and statement B (“I have a cat”) need to be true—it’s not enough to have only one or the other.

Let’s look at another truth table…this time for the word “or:”

or truth table
The truth table for the word “or.”

Unlike A and B, fulfilling A or B only requires one statement to be true. But note that if both statements are true, then the statement A or B is also true. We usually think of the word “or” as exclusive—something has to be either, not both. In Boolean logic, however,  the only way that “I have a dog or I have a cat” is false is if I have neither pet.

The truth table for the word “not” (below) is very simple, since we only negate one statement, rather than combining two statements. If A (“I have a dog”) is true, then not A (“I don’t have a dog”) is false. The converse is also correct: If A is false, then not A is true.

not table
The truth table for the word “not.”

We can even encode the notion of causality into our truth tables. Let’s try making a truth table for the idea of “if A, then B“—for example, “If I am blogging, then I am using a computer.” Here’s the table:

A implies B
The truth table for the statement “If A, then B.”

So statement A is “I am blogging” and statement B is “I am using a computer.” The first row says that, if I’m both blogging and I’m using a computer, then the statement “If I’m blogging, then I’m using a computer” isn’t disproved and is therefore true in this scenario. The second row says that, if I’m somehow blogging without using a computer, this means that if A, then B is false because it makes a wrong assumption: that the only possible way to blog is to use a computer. The third and fourth rows are fail-safes against logical fallacy. Even if I use a computer for activities other than blogging, that has nothing to do with whether or not I blog on a computer. Thus, the third row tells me that, if I’m not blogging but I am using a computer, the statement “If I’m blogging, then I’m using a computer” is still true. Similarly, the fourth row tells me that, if I’m neither blogging nor using a computer at the moment, the statement “If I’m blogging I’m using a computer” is still true.

Resist the urge to object, “But we can’t come to any conclusion about the relationship between blogging and computer use unless you’re blogging!” Unlike in real life, there is no “maybe” or “it depends” or “I don’t know” option in Boolean logic. That’s because the only thing we’re examining when we look at if A, then B is the idea that B must happen if A happens. Therefore, the only way to get a false is to disprove that assumption by showing that A can happen without B happening. If that assumption isn’t tested, our evaluation stays at its “default” value of true.

The third and fourth rows of this truth table are interesting for another reason. They open the door to what logicians call a vacuously true statement, which is an if A, then B statement whose A is never true. Since A is never true, then the truth table tells me that the statement if A, then B is always true. For example, if I said “if there is a tree on the moon, then that tree is purple,” then Boole would tell me that my statement is completely true. The reason is that, of course, there are no trees on the moon.

This sort of reasoning is wildly unintuitive to people not used to thinking in terms of Boolean logic. It doesn’t seem logical at all! However, if we want to be consistent, we are forced to think in this way.

Next time, I’ll continue the story of Boolean logic by telling you how to build up complex statements like you might encounter in real life.

Related Reading

  • Boolean logic is the topic of many first-year college computer science and mathematics courses around the world. If you’re interested in learning it at a deeper level, here’s an online course you can take.
  • A good place to start is Wikipedia’s page on Boolean logic.
  • Some math bloggers have attempted to describe Boolean logic with more depth. I particularly like professional math tutor John M.’s article. You can find it here.

You May Also Enjoy

If you liked this post, you might enjoy my other posts on mathematics:

Posted in abstract algebra, logic, Mathematics, Science And Math | Tagged , , , , , , | 13 Comments

How Planets Form

The Heavenly Spheres make music for us,
The Holy Twelve dance with us,
All things join in the dance!
Ye who dance not, know not what we are knowing
~Gustav Holst

By the sweat of your brow you will eat your food
until you return to the ground, since from it you were taken;
for dust you are and to dust you will return.
~Genesis 3:19

Artist's conception of planet formation
Artist’s conception of the formation of planets around the star Beta Pictoris. (Image originally due to NASA. Found on Wikipedia.)

Many months ago, Richard Green posted an article on Google+ that described how life on a toroidal planet would work. The discussion in the comments eventually led to speculation as to whether or not it’s possible for such a toroidal structure to actually form. That discussion is what inspired this post. Today, I’ll tell you about the nebular hypothesis, astrophysicists’ current best theory about how planets form. (Fun historical fact: One of the first people to propose the nebular hypothesis was philosopher Immanuel Kant.)

A torus planet.
A torus-shaped planet. Could such a thing actually form? Sadly, the answer seems to be “no.”  (Source for the background image.)

In The Beginning, Dust

Our solar system probably started as a huge cloud of gas and dust, like a nebula (hence the name “nebular hypothesis”). The particles of dust and wisps of gas gravitationally attracted each other, and other time, the denser clouds of matter collapsed into themselves. As the density of each cloud increased, so did its temperature. Eventually it became so dense and so hot that it became what we call a protostar—a young, vigorous, and confused star.

But not all of the gas and dust had become part of the protostar yet. As the protostar began to age, it began to attract and eat the remainder of the gas. Over time, as the remaining gas fell into the star, it formed a disk, as shown below. Near where the disk touched the star, the compression of its gas superheated it, generating jets of energy pointing out from the star. (For experts: The reason the gas formed a disk is because it had to jet its angular momentum before it could fall in.)

protostar
A newborn protostar feasts on the delicious gas in its accretion disk. Image due to NASA. Found on Wikipedia.

It’s All In The Disk

Let’s talk about the disk some. For reasons that will soon become clear, these disks are called protoplanetary disks. Not everything in the disk orbited around the star at the same speed. As dust and gas particles whizzed past each other, sometimes they collided…and sometimes they stuck to each other, forming bigger particles.

Over millions of years and trillions of sticky collisions, these dust particles grew to several kilometers in diameter, forming small objects that we call planetesimals. At this size, these planetesimals had a gravitational pull strong enough to attract many dust particles, allowing them to grow even faster. Very likely, planetesimals also collided with each other to form even larger objects. Eventually, these bodies were large enough to be called planets.

This description tells us that toroidal planets cannot form. Planetesimals grow in size from collisions with dust and with each other. It seems very unlikely that they would form a shape other than “roughly spherical.”

The End of the Disk

After enough time passed and the protostar had feasted sufficiently, it would begin to emit a blast of light and subatomic particles called the solar wind. This pressure blew away all remaining gas and dust in the disk that hadn’t already coalesced into large objects—leaving behind the collection of planets we know as the solar system.

Evidence

Obviously, we can’t look back in time to see how our own solar system formed. But we can look out into space to try and find solar systems that are in the process of forming. Protostars are easy to capture on film because the jets that they fire have a characteristic shape. We call them Herbig-Haro objects, and they produce some staggeringly beautiful images. See the photos below:

Herbig-Haro objects
Some Herbig-Haro objects. Image courtesy of Wikipedia.

We can also observe the protoplanetary disks that are feeding the protostar. At first, they were hard to spot and we had to use some fancy image enhancement techniques to see them, as in the figure below. The top row shows the unenhanced images and the bottom row shows the enhanced images.

Some protoplanetary disks
Some protoplanetary disks captured by the Hubble Space Telescope. We’ve managed to see what they really are using fancy image enhancement techniques. Image due to NASA. Found on Wikipedia.

However, the Hubble got an upgrade, and we’ve been looking a while. We now have some much better images. Look at the figures below. See those little tadpole-like objects? Those are protoplanetary disks.

more protoplanetary disks
Some prettier images of protoplanetary disks taken by the Hubble telescope. Image courtesy of NASA. Found on Michael Richmond’s course website.

Hubble has now captured more than 150 images of protostars and their jets and disks. A few more for your viewing pleasure:

MOAR disks
Even more images of protoplanetary disks. Image courtesy of NASA. Found on Michael Richmond’s course website.

Sadly, we’re far too distant to see if the disks contain planetesimals.

Issues

I want to emphasize that the nebular hypothesis of planet formation is currently still a hypothesis. It’s the best description we have for how planets formed in our solar system, but it still has some important issues that need to be worked out.

For example, we still don’t know how gas giants like Jupiter form. The planetesimal description relies on the planetesimals being made of rock, so this only describes the formation of terrestrial planets like Earth and Mars. Additionally, the nebular hypothesis predicts that planets should emerge from the disk in very erratic orbits. It’s not clear how they form their current elliptical orbits, which are very regular.

Only time will tell, I suppose, if the nebular hypothesis is correct.

Related Reading

Posted in Astrophysics, Physics, Science And Math | Tagged , , , , , , , | 1 Comment

The Graphene Electro-Optic Modulator

graphene eom pretty
A graphene-based electro-optic modulator made by Chien-Chung Lee and Seiya Suzuki in the Schibli lab.

Say we have a beam of light—maybe we made it with a laser. We’d like be able to change the intensity of the beam so that we can alternately brighten and dim it. Moreover, we’d like to be able to do so quickly. Physically blocking and unblocking the beam just isn’t fast enough. So what do we do?

The solution is to make an electric switch so we can change how the light behaves via electrical signals. This is an electro-optic modulator (EOM). Two weeks ago, I introduced graphene to you all. And last week, I described some of the work I did on graphene as an undergraduate student in the Schibli lab. This time, I’ll explain the ultimate product of that research: a graphene-based electro-optic modulato like the one shown in the figure above. I want to emphasize that I didn’t build this device and I take no credit for its design. I did, however, do some experiments that helped prove that such a device was possible. I’ll talk about all of that today.

(Important side note: one can also make an acousto-optic modulator, which uses sound to change how light behaves.)

The Strange Dance of Light and Matter

Before I can tell you how a graphene EOM works, I need to briefly discuss how a material absorbs light. I’ve given fairly detailed explanations of absorption in the past. But today I want to focus on other things, so I’ll only be presenting a very rough, inaccurate picture of what goes on. Take it with a grain of salt.

We know from James Clerk Maxwell that light is a wave made of electric and magnetic fields. These fields feed into each other and wiggle back and forth, as shown below.

Light as an electromagnetic wave
Light as an electromagnetic wave. The red lines represent an electric field and the blue lines represent a magnetic field. A changing electric field induces a changing magnetic field, which, in turn, induces a changing electric field. (source).

Electrons carry negative charge and are thus affected by electromagnetism. So when light passes through a material, its wiggling pushes the electrons around, accelerating them. But when an electron is accelerated, it leeches energy out of the light. This is absorption.

(Things are much more complicated than this, of course. In insulators, this wiggling causes all sorts of other things to happen to the light. It can bend, slow down, or change direction. We call this refraction, which I’ve written about before here. In a conductor, the light will probably be reflected.  Also, absorption is actually a quantum-mechanical effect.)

The Obstacles

To absorb the light, our electrons must be free to wiggle around. But many electrons aren’t free to wiggle in this way. The material might be too crowded, so that an electron that “wanted” to move would be trapped by all the other electrons in its way. Or an electron might be too tightly bound to the atomic nucleus to be able to wobble. This means that, if we can figure out how to control how mobile electrons are in a material, we can control how absorptive it is!

Chemical Doping

Now let’s talk about graphene. In its natural state, graphene has many electrons that are free to wobble (and thus absorb light). However, let’s say we pour some nitric acid on our graphene. Acid eats things because each acid molecule breaks into two pieces: a negatively charged anion and a single hungry proton (a positive hydrogen ion) that wants to chemically react with anything it can find.

Graphene is too tough for the acid to eat, but the proton still has an effect. It lands on the surface of the graphene, attracts one of the electrons within the graphene, and bonds to it. The electron stays within the graphene, but becomes immobilized so that it can’t wiggle around anymore, as shown below. One less electron to wiggle means one less electron to absorb any light that passes through the graphene, so this causes the whole graphene piece to become less absorptive. This process is called p-doping because we place positive charge on the surface of the graphene.

acid doping. No not that kind, silly!
Doping graphene with nitric acid. The acid breaks down into an HNO3 anion and a proton (a.k.a. a hydrogen cation). The proton lands on the graphene and bonds with an electron in the material, immobilizing it.

If we had used a base instead of an acid, we could have played the same game. The base’s negatively charged ion would have latched onto the graphene and bonded with one of its protons, which would free up an electron. If the graphene had already been p-doped, this might make the graphene more absorptive. If the graphene started in its natural state, the newly freed electron might crowd out its peers and make the material less absorptive. This process is called n-doping because we place a negative charge on the surface of the graphene.

(I’m glossing over a lot. The real story of doping involves the band structure of a material. I wrote about that here.)

So if we shine light through a graphene sheet, we can control how much of the light it absorbs by adding protons (p-doping) or removing them (n-doping).

Electrostatic Doping

Now remember, we’re trying to make an electro-optic modulator: a device that lets us quickly control how much light passes through it depending on an electrical signal. For our purposes, adding acids and bases is much too slow. We need a new trick. Is there any way we can mimic chemical doping?

As it turns out, there is! Say we place a sheet of graphene on top of some glass and sandwich our glass between two metal places, as shown below. If we apply a voltage across the plates, we can push electrons onto the graphene and charge it up. The result is that graphene now has more electrons, and they crowd each other out, preventing them from moving or absorbing.This process is called electrostatic doping, and it’s exciting because we can turn its effects on and off as fast as we can turn the voltage on and off.

A graphene electro-optic modulator
Electrostatic doping of graphene. If we sandwich a piece of glass between graphene and a metal plate and apply a voltage across the two, we can charge up the graphene and control the number of electrons in it and thus control the absorption.

Electro-Optic Modulator

Now this is an effect fast enough to make an electro-optic modulator. In the Schilbi Lab, where I worked as an undergraduate student, Professor Thomas Schibli and his students Chien-Chung Lee and Seiya Suzuki placed a piece of tantalum oxide—which has nicer properties than glass—on top of an aluminum mirror. On top of that, they put a sheet of graphene. And on top of that, they placed a ring of aluminum, as shown below. (The shape was a ring so that light could pass through the center.) When they applied a voltage between the ring of aluminum and the mirror, they were able to electrostatically dope the graphene and change how much light it absorbed.

a diagonistic electro-optic modulator
A diagram of a graphene electro-optic modulator. We sandwich graphene and tantalum pentoxide between an aluminum mirror and an aluminum ring. Then we apply a voltage between the mirror and the ring.

It worked beautifully! Below is one of the devices actually made in the lab. On the left is an optical photograph of the device through a microscope. On the right is a two-dimensional color-plot of the “modulation depth,” which is a measure of how much the graphene’s absorption changes over time. The brighter the color, the bigger the modulation depth in that spot.

Schibli lab electro-optic modulator
A graphene-based electro-optic modulator made in the Schibli lab. (a) An actual photograph of the device. (b) A plot of modulation depth.

My Part in All of This

I take no credit for the idea of using graphene for an electro-optic modulator—that was all Professor Schibli. I also take no credit for tackling the engineering challenges of designing and building one—that was all Chien-Chung Lee and Seiya Suzuki. What I did was help prove this device could work before they started building it. I grew graphene samples and then Chien-Chung doped them with acid and measured their absorption. While the samples were still doped, I measured their Raman spectra to prove that the acid was having the expected doping effect. Afterwards, I looked at the Raman spectra again to look for signs of acid damage.

I did have the privilege, however, of seeing a working device. The team managed to get one functional while I was writing my undergraduate honors thesis on what I’d done. Pretty neat, huh?

Further Reading

  • This is part three of a three-part series on graphene. If you missed them, you can find the first and second parts of the series here and here.
  • I glossed over many, many details here. The true story of how doping works is rooted in the band structure of a material. I talk about that here.
  • I also glossed over important aspects of how light and matter interact. I’ve covered these in several articles, but a good place to start is my article on refraction.
  • The quantum mechanics of absorption is first detailed in my article on the Bohr model of the atom.
  • I also talk about the interaction of light and matter in my article on lasers, my article on mode-locking, and my articles on scattering, which you can find here and here.
  • If you’re very brave, you can look at my honors thesis, which explains all of this in extreme detail.
  • I am a co-author on a paper detailing the proof-of-concept work. Sadly, it’s behind a paywall, but you can get it here if you have a journal subscription.
  • The Schibli group also published a paper on the modulator. It’s behind a paywall too, but if you have a journal subscription, you can find it here.
Posted in Condensed Matter, optics, Physics, Quantum Mechanics, Science And Math | Tagged , , , , , , , | Leave a comment