What a program can do

Code first. Below this paragraph is a program one line long. Press “Run”.

While you were reading that sentence, the line flew to our server. There a sandbox, a small isolated computer, was started up for it; Python ran the command, and the answer came back to you. The two asterisks ** mean “to the power of.” On the screen is the product of a thousand twos, all 302 of its digits. A phone calculator would show the first few digits and fall back on scientific notation, which is only an approximation.

The code in this book is there to be changed. Click the line, replace 1000 with a number of your own (10000, say) and run it again. You can’t break anything: every cell runs in a disposable sandbox that the server throws away after the run. The button with the circular arrow brings back the original code.

Next come five surprises. We won’t explain them yet; that’s what the other 65 chapters are for. For now it’s enough to see what computer science looks like before we start building it.

Surprise one: twenty questions

Think of a whole number between one and a million. Any number: your apartment number, the year your grandmother was born, the view count of your latest video. The machine will ask questions of the form “Is it greater than…?” and you answer them honestly. Want to bet it won’t need more than twenty?

Twenty questions are enough for a million possibilities because every answer throws away half of the numbers that are left. After the first question there are half a million, after the second two hundred and fifty thousand, after the tenth fewer than a thousand, after the twentieth one. Double one twenty times and it passes a million: $2^{20} = 1\,048\,576$.

Here is the same game as a Python program. Run it, and the server will ask its questions in a box under the code. While you think, the program sits on the server and waits for your answer.

There is no brute force in this program. Had it asked in order (“Is it 1? Is it 2? Is it 3?”), it would have needed a million questions in the worst case. Instead, on the same computer, twenty will do: the idea makes all the difference. The idea has a name, binary search, and you’ll meet it again and again: it is how you find a word in a dictionary, the commit that introduced a bug in a project’s git history, a row among a billion in a database.

Surprise two: the race

Take a job computers do all the time: putting numbers in increasing order. Below are two sorting programs. The first, “bubble,” walks along the list swapping neighbors that are out of order until no such pair is left. The second, “merge,” cuts the list in half, sorts the halves and merges them, like two decks of cards.

On sixty-four numbers the difference is visible but not alarming. The program below takes five thousand random numbers, sorts them both ways and times each on the server.

Merge wins by a factor of tens, sometimes hundreds. Before you read on, guess what happens to bubble on a bigger list.

A processor twice as fast makes bubble sort twice as fast; a different idea makes sorting thousands of times faster, and the more data there is, the bigger the gain. That is why programmers think so hard about algorithms. People invent them, sometimes before the machines exist: John von Neumann described merge sort in 1945, when no computer that could run it had yet been built.

Surprise three: a tree from a dozen lines

Programs do more than count. The next one draws on your page, even though it runs on the server: Python sends commands like “step forward, turn, lift the pen,” and the browser shows a turtle carrying them out.

The function branch draws a trunk and then… calls itself twice, for a left and a right branch, each almost a third shorter. Those call themselves too, nine levels deep, until there are 511 branches. No line of the program says where the 300th branch will go: the tree grows out of a rule. The technique is called recursion, and a few chapters from now you’ll be drawing pictures like this yourself. For now, try changing 25 to 40 and 0.72 to 0.6.

Surprise four: a program that prints itself

Students used to rack their brains over this one: write a program that prints its own text, character for character. Reading the file from disk is cheating. At first sight it can’t be done: to print its text, the program has to contain that text, so it would have to be longer than itself.

Yet in Python such a program is two lines long. Run it, and a comparison with the source will appear under the output.

The string s is a template of the program with a hole in the middle, and into the hole the program puts… the string itself. Programs like this are called quines. Douglas Hofstadter coined the name in Gödel, Escher, Bach, after the philosopher Willard Van Orman Quine, who studied sentences that talk about themselves. Change even one character of the program and the match breaks; then think about how to repair it. We’ll take the quine apart in Chapter 7: it is the first of the course’s big questions.

A program that talks about itself will come back. In Chapter 56 a similar self-reference will lead us to one of the deepest results in the theory of computation: there are questions about programs that no computer can answer.

Surprise five: three lines nobody understands

Take any positive whole number. If it is even, halve it. If it is odd, multiply it by three and add one. Do the same with the result, and so on.

From 6 you get 3, then 10, 5, 16, 8, 4, 2, 1. From 7: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. It looks as if every number sooner or later rolls down to one. Try 27.

Modest 27 shoots up to 9232 and comes down to one only after 111 steps. Its neighbors take quite different paths:

Does every number get to one? That is the Collatz conjecture, and it is almost ninety years old. Computers have checked every number up to $2^{71}$, more than two thousand billion billion of them, and each one got there. But no amount of checking proves it: somewhere further on there may be a number that flies off to infinity or falls into a loop. Paul Erdős, one of the most prolific mathematicians of the twentieth century, is reported to have said of it: “Mathematics may not be ready for such problems.”

The question is an odd one. We aren’t asking what the program computes; we are asking whether it ever finishes. For three lines about numbers, nobody knows. Whether such a question can be answered for any program at all you’ll find out in Chapter 56, and it is one of the biggest surprises of the course.

So what is computer science?

None of the five surprises is about the computer itself. Binary search works in a paper dictionary, von Neumann invented merge sort on paper, the quine is a question about language, the Collatz conjecture a question about numbers. The computer is there so that we can try all this, quickly and on a large scale.

There is a saying, usually credited to Edsger Dijkstra: “Computer science is no more about computers than astronomy is about telescopes.” Nobody has found it in Dijkstra’s writings and its author is unknown, but the thought is right. Computer science studies computation: what can be computed, how to do it quickly and reliably, how the machines that compute are built, and where the limits of computation lie.

The course is built as a descent and a climb. First you’ll learn to write programs and to think in algorithms. Then you’ll go down from a line of Python to the processor and the switches it is made of. Then you’ll climb back up: the operating system, networks, databases, programming languages. In Part VIII you’ll write a compiler for your own teaching computer, Iskra-8, which you’ll have built in Part IV. And at the end you’ll ask what no computer can ever do, and find out how ciphers are built on it.

Eleven questions the course will answer

Each part of the course has a big question of its own, something like a puzzle, and the part ends with the answer. You won’t have to wait until the end: the first answer comes as early as Chapter 7, and then one every six chapters or so.

1. Can a program print itself? You’ve just seen that it can. How it works we’ll take apart in Chapter 7, once we can work with text.
2. Why does one program solve a problem in a second while another wouldn’t finish before the end of the universe? You saw it in the race. We’ll learn to work out speed in advance in Chapter 13.
3. How does a navigation app find the shortest route among millions of roads in a second? We’ll build one ourselves, in Chapter 24.
4. How do you make a computer out of switches? We’ll put one together from logic gates, in Chapter 32.
5. How do a hundred programs run on two cores without wrecking each other’s data? Chapter 39.
6. How do billions of computers work together when none of them is in charge? Chapter 44.
7. How does a search engine find what you need among billions of pages in a fraction of a second? We’ll build a search engine for the textbooks on this site, in Chapter 48.
8. How does one program understand another? You’ll write an interpreter and a compiler for your own machine, in Chapter 52.
9. Are there problems no computer can solve? Yes, there are, and the proof fits on a page: Chapter 56.
10. How do you agree on a secret when every word is overheard? Chapter 60.
11. Can a machine learn what nobody taught it? Chapter 63.

How the cells and tasks work

All you need for the course is this browser. There is nothing to install: our server runs the code.

• Run sends the code to the server; the output comes back line by line as the program works. Ctrl+Enter (⌘+Enter on a Mac) does the same from the editor.
• If the program asks for something with input(), a box for your answer appears under the code.
• Steps records the run and lets you walk through the program line by line: you see which line is running, which variables exist and what they point to. It comes in especially handy in the chapters on functions and recursion.
• The server sets limits for every program: ten seconds, 256 MB of memory, no internet. An infinite loop won’t hang the page or the server; the time limit stops it.
• Tasks differ from cells in having a “Check” button: the server runs your solution against hidden tests and shows the input it got wrong. Your progress is saved in this browser and shows up on the page with all the tasks.

The first task is a very easy one. Give it a try.

What next

So far you have been running other people’s code. In the next chapter you’ll start writing your own, and almost at once you’ll see red text on the screen. It happens to everyone: the 1843 program often called the first ever published already had a bug in it, and next to the word “bug” in the logbook of one of the first computing machines someone taped a real moth. How to talk to a machine that takes every word literally, and how to read its complaints, is the subject of Chapter 1.