Chapter 1: What Is Computation?

1.1 Bits: The Atoms of Information

Imagine you are in a dark room with a single light switch. The switch can be in one of two positions: off or on. That single choice - off or on, no or yes, false or true, 0 or 1 - is the fundamental unit of information. We call it a bit, short for binary digit.

One bit is not very expressive on its own. With a single bit you can say "yes" or "no," but not much else. The power of bits comes from combining them. With two bits you can represent four distinct values: 00, 01, 10, and 11. With three bits you get eight values: 000, 001, 010, 011, 100, 101, 110, 111. The pattern is precise: $n$ bits can represent $2^n$ different values. Eight bits make a byte, giving you $2^8 = 256$ possible values - enough to encode every letter in the English alphabet (uppercase and lowercase), the digits 0 through 9, punctuation marks, and still have room to spare.

Binary and Decimal

In everyday life we use the decimal (base-10) number system. The number 42 means $4 \times 10^1 + 2 \times 10^0$. The binary (base-2) system works exactly the same way, but each digit position represents a power of 2 instead of a power of 10. The binary number 101010 means:

So the decimal number 42 and the binary number 101010 represent the same quantity - they are just written in different bases. Every number you know from daily life has a binary equivalent, and converting between the two is purely mechanical.

Encoding Everything as Bits

Numbers are an obvious fit for binary, but bits can encode anything once we agree on a scheme. Text? Assign each character a number (the letter "A" is 65, "B" is 66, and so on in the ASCII standard). Colors? Store how much red, green, and blue light to mix - each as a number between 0 and 255. Sound? Sample the air pressure thousands of times per second and record each sample as a number. Images, video, your location on a map - all of it reduces to long sequences of zeros and ones.

Try the converter below to build intuition for how decimal and binary relate to each other. Type a decimal number and see its binary form, or type a binary string and see the decimal value.

1.2 Logic Gates and Boolean Algebra

Storing bits is useful, but computation requires transforming them. The simplest transformations are performed by logic gates - tiny circuits that take one or two input bits and produce an output bit according to a fixed rule. There are only a handful of fundamental gates, and from these few building blocks every computation that has ever run on any computer is ultimately constructed.

The NOT Gate

The simplest gate is NOT. It takes a single bit and flips it: 0 becomes 1, and 1 becomes 0. In Boolean algebra we write $\text{NOT}(A)$ or $\overline{A}$ or $\lnot A$. Think of it as flipping a light switch.

The AND Gate

The AND gate takes two input bits and outputs 1 only when both inputs are 1. If either input is 0, the output is 0. In everyday language, "I will go to the park if it is sunny AND I have free time" - both conditions must be true. We write $A \land B$.

The OR Gate

The OR gate outputs 1 if at least one of its inputs is 1. "I will be happy if I get a raise OR win the lottery" - either one suffices (and both at once is fine too). We write $A \lor B$.

The XOR Gate

XOR (exclusive or) outputs 1 when the inputs are different. If both inputs are the same (both 0 or both 1), the output is 0. A handy mnemonic: "one or the other, but not both." We write $A \oplus B$.

Boolean Algebra

Just as ordinary algebra lets you manipulate equations with $+$ and $\times$, Boolean algebra lets you manipulate logical expressions with AND, OR, and NOT. A few useful identities:

• Identity: $A \land 1 = A$ and $A \lor 0 = A$
• Null: $A \land 0 = 0$ and $A \lor 1 = 1$
• Complement: $A \land \overline{A} = 0$ and $A \lor \overline{A} = 1$
• De Morgan's laws: $\overline{A \land B} = \overline{A} \lor \overline{B}$ and $\overline{A \lor B} = \overline{A} \land \overline{B}$

De Morgan's laws are especially important. They tell us we can always swap ANDs for ORs (and vice versa) as long as we also flip the inputs and the output. This flexibility means we can build any logical function from just NAND gates (NOT-AND) or just NOR gates (NOT-OR) - a fact that greatly simplifies hardware manufacturing.

Use the interactive truth table below to explore how different gate types behave. Select a gate and watch how the output column changes for every combination of inputs.

1.3 Building Circuits from Gates

A single logic gate is like a single word - useful, but limited. The real expressive power comes from combining gates into circuits, just as words combine into sentences and paragraphs. Let us build up from the simplest useful circuit to something that can genuinely add numbers.

The Half Adder

Suppose we want to add two single-bit numbers, $A$ and $B$. Each is either 0 or 1, so the possible sums are:

Notice two things. First, the sum bit $S$ follows the XOR pattern: it is 1 when the inputs differ. Second, the carry bit $C$ follows the AND pattern: it is 1 only when both inputs are 1. So:

This tiny two-gate circuit is called a half adder. It adds two bits and tells you the single-digit result (the sum) and whether there is a carry.

  A ----+--[ XOR ]---- S  (sum)
        |
  B --+-+--[ AND ]---- C  (carry)
      | |
      +-+

But a half adder has a limitation: it only handles two inputs. When adding multi-digit binary numbers column by column (just like you do in long addition), each column after the first might also receive a carry from the previous column. We need a circuit that can add three bits.

The Full Adder

A full adder takes three inputs - $A$, $B$, and $C_{in}$ (the carry from the previous column) - and produces a sum bit $S$ and a carry-out bit $C_{out}$. You can build it from two half adders and an OR gate:

1. First half adder: compute $A \oplus B$ (partial sum) and $A \land B$ (first carry candidate).
2. Second half adder: add $C_{in}$ to the partial sum from step 1, producing the final sum $S$ and a second carry candidate.
3. OR gate: the carry-out is 1 if either carry candidate is 1.

          +-------+
  A ------| Half  |--- partial sum --+-------+
  B ------| Adder |--- carry1       -+       |
          +-------+                  |       |
                                     |  +-------+
  C_in ------------------------------|--| Half  |--- S
                                     |  | Adder |--- carry2
                                     |  +-------+
                                     |       |
                              carry1-+--[ OR ]---- C_out
                                        carry2

Ripple-Carry Adder

Now chain several full adders together, with each carry-out feeding into the next column's carry-in, and you have a ripple-carry adder - a circuit that adds multi-bit binary numbers. An 8-bit adder uses 8 full adders in a chain. A 64-bit adder (the kind inside your laptop's processor) uses 64. The principle is identical to how you learned to add multi-digit numbers in school, carrying from one column to the next.

Beyond Adders

The same approach scales to every arithmetic and logical operation a computer needs. Subtraction can be performed with adders (using a trick called two's complement). Multiplication is repeated addition. Comparison of two numbers is done by subtracting them and checking whether the result is zero. Circuits called multiplexers select between different data paths, acting like railroad switches for information. A decoder takes a binary number and activates exactly one of many output lines - perfect for addressing memory locations.

Every one of these circuits is, at bottom, just a carefully arranged collection of AND, OR, NOT, and XOR gates. There is nothing magical happening inside a computer chip - only billions of these simple gates working in concert, flipping bits according to their fixed rules.

1.4 From Circuits to Computers

We have seen that gates combine into circuits, and circuits can add, subtract, compare, and route information. But a calculator that only adds is not a computer. What makes a computer fundamentally different is programmability - the ability to follow different sequences of instructions without being physically rewired.

Layers of Abstraction

Between the raw logic gates and the apps on your phone lies a tower of abstraction layers:

1. Transistors. Microscopic electronic switches - the physical implementation of our abstract 0s and 1s. Modern chips contain billions of them, each smaller than a virus.
2. Logic gates. Transistors wired together to perform AND, OR, NOT, and so on.
3. Functional units. Gates assembled into adders, multipliers, comparators, and memory cells.
4. Processor (CPU). Functional units organized around a central loop: fetch an instruction from memory, decode what it means, execute it, and repeat.
5. Operating system. Software that manages hardware resources and provides a stable platform for applications.
6. Applications. The programs you actually interact with - web browsers, games, messaging apps.

Each layer hides the complexity of the layers beneath it. When you write a text message, you do not think about transistors. When an operating system schedules tasks, it does not think about individual logic gates. This principle of abstraction is what makes it possible for humans to build systems of staggering complexity without drowning in details.

The Stored-Program Concept

The great intellectual leap that created modern computing was the realization that instructions and data are both just sequences of bits and can be stored in the same memory. This is the stored-program concept, articulated by John von Neumann in his famous 1945 draft report on the EDVAC computer (though the idea had many contributors, including Alan Turing and the builders of the earlier ENIAC).

The processor runs a deceptively simple loop, over and over, billions of times per second:

1. Fetch the next instruction from memory (the address is tracked by a special register called the program counter).
2. Decode the instruction to figure out what operation to perform and which data to use.
3. Execute the operation - perhaps adding two numbers, comparing values, or jumping to a different instruction.
4. Store the result back into a register or memory, and advance the program counter.

That is it. Every computation your computer has ever performed - every web page rendered, every email sent, every video decoded - is the result of this fetch-decode-execute cycle running at extraordinary speed.

Memory and the Speed Hierarchy

A processor is only as fast as its ability to feed data to its circuits. Modern computers use a memory hierarchy to balance speed and cost:

• Registers - a tiny number of storage slots right inside the processor, blindingly fast but very few (typically 16 to 32 in a modern CPU).
• Cache - a small, fast memory sitting close to the processor, acting as a staging area for frequently used data.
• Main memory (RAM) - gigabytes of storage, fast enough for most tasks but slower than cache.
• Storage (SSD/HDD) - terabytes of persistent storage, thousands of times slower than RAM but retaining data when the power is off.

The processor tries to keep the data it needs most in the fastest layers. When it must reach down to a slower layer, the resulting delay is called a cache miss. Understanding this hierarchy is important for writing efficient programs, but for our purposes the key takeaway is that all of these layers ultimately store bits - and those bits are all manipulated by the same kinds of logic gates we discussed earlier.

1.5 What Makes a Problem "Hard"?

We now know that a computer is, at its core, a machine that flips bits according to rules at tremendous speed. Modern processors perform billions of operations per second. With that kind of raw power, is there any problem a computer cannot solve? The perhaps surprising answer is: yes, many. And understanding why is the thread that will eventually lead us to quantum computing.

Measuring Difficulty: Time Complexity

Computer scientists measure the difficulty of a problem not by how long a specific program takes on a specific machine, but by how the required time grows as the input gets larger. This is called time complexity, and we express it using big-O notation.

Suppose you have a list of $n$ names and need to find a particular one. If the list is unsorted, you might have to check every name, one by one - the time grows in proportion to $n$. We say this has $O(n)$ time complexity (read as "order n" or "linear time"). If you double the list size, the work roughly doubles - not ideal, but manageable.

Now suppose the list is sorted alphabetically. You can use binary search: open the list to the middle, check whether your target comes before or after, and eliminate half the list in one step. Repeat, and you find the name in about $\log_2 n$ steps. That is $O(\log n)$ time - astonishingly efficient. A sorted phone book with a million names requires only about 20 comparisons.

Easy Problems: The Class P

Many important problems can be solved in polynomial time - meaning the number of steps grows as some fixed power of the input size, like $O(n)$, $O(n^2)$, or $O(n^3)$. These problems form the complexity class called P (for "polynomial"). Sorting a list, finding the shortest route on a map, multiplying two numbers, searching a database - all are in P. For problems in P, bigger inputs mean more work, but the growth is tame enough that computers can handle impressively large instances.

Hard Problems: The Class NP

Now consider a different kind of problem: a jigsaw puzzle. Putting it together might take a long time, but if someone hands you a completed puzzle, you can verify it is correct almost instantly - just check that all pieces fit. Many important problems share this property: hard to solve, but easy to check.

The class NP (nondeterministic polynomial) contains all problems where a proposed solution can be verified in polynomial time, even if finding that solution might take much longer. Every problem in P is automatically in NP (if you can solve it quickly, you can certainly verify a solution quickly), but NP also contains problems for which no fast solving algorithm is known.

The P vs NP Question

The biggest open question in computer science is: does P equal NP? In other words, if a solution to a problem can be quickly verified, does that guarantee it can also be quickly found? Almost all computer scientists believe the answer is no - P does not equal NP - but no one has been able to prove it. There is even a million-dollar prize from the Clay Mathematics Institute for a proof either way.

Exponential Walls

Why does this matter? Consider the problem of factoring large numbers. Given the number 15, you can quickly find that $15 = 3 \times 5$. But given a number with hundreds of digits (the product of two large primes), the best known classical algorithms take time that grows exponentially - roughly $O(2^{n^{1/3}})$ for an $n$-digit number. This exponential growth creates an impenetrable wall: factoring a 600-digit number could take longer than the age of the universe on today's fastest supercomputers.

This difficulty is not just academic. The security of much of the internet relies on the assumption that factoring large numbers is hard. Your bank transactions, encrypted emails, and secure web connections all depend on it.

A Landscape of Complexity

Time complexity paints a rich landscape. Here is a simplified map of how some growth rates compare for an input of size $n$:

The jump from polynomial to exponential is dramatic. For $n = 100$, an $O(n^2)$ algorithm does ten thousand operations - trivial for a modern computer. An $O(2^n)$ algorithm would require roughly $10^{30}$ operations - more than the number of grains of sand on Earth, more than the number of seconds since the Big Bang, multiplied together. No amount of engineering can overcome exponential growth through brute force alone. We need fundamentally new ideas.

Quantum computing is exactly that: a fundamentally new model of computation based on the laws of quantum mechanics. In the chapters ahead, we will see how quantum computers exploit phenomena like superposition and entanglement to solve certain problems that are intractable for classical machines. But before we can appreciate what makes quantum computing revolutionary, we needed to understand what classical computation is, what it can do, and where it hits a wall.

That understanding is now in your hands. You know that all information reduces to bits; that bits are transformed by logic gates; that gates compose into circuits which compose into full computers; and that even these extraordinary machines have fundamental limitations. With this foundation firmly laid, we are ready to explore the mathematics of information in Chapter 2, and then the surprising world of reversible computing in Chapter 3 - which will be our bridge into the quantum realm.

Chapter 1 Review