by Martin Erwig
instance. An instance of an abstractionG is obtained by the substitutionF of arguments for the parametersA in the definition of the abstraction.
interface. A name plus parametersA that is assigned to an abstractionG to facilitate its use.
lambda calculus. A languageD abstractionG for algorithmsA. If the Church-Turing thesisG is true, any algorithm can be expressed as a lambda calculus programA. In its expressiveness to describe algorithms and computationA, lambda calculus is equivalent to a Turing machineG.
premise. A part of a typing ruleG that must be true for the conclusionG of the typing rule to hold.
static type checking. Checking typesG before executingA an algorithmA.
Turing machine. An abstract machineG for computersA. Serves as a mathematical model of computationA. In this regard it is equivalent to lambda calculusG. If the Church-Turing thesisG is true, any algorithmA can be translated into a programA for a Turing machine.
type. A data abstractionG that provides a unifying description for a group of representationsA.
type checker. An algorithmA that checks whether another algorithm violates any typing rulesG.
typing rule. A rule for constraining the admissible inputsA and outputs of algorithmsA that can spot mistakes in algorithms. Can be checked automatically by a type checkerG.
Concept How It Appears in Harry Potter
Abstract machine —
Abstraction Potion, Marauder’s map
Axiom Muggles cannot perform magic
Church-Turing thesis —
Conclusion …, he or she can cast spells
Data abstraction The types of wizards and muggles
Dynamic type checking Trying a spell without checking the requirements
Functional abstraction Spells
Instance Using Wingardium Leviosa spell on a feather
Interface A spell has a name and needs a wand and an incantation
Lambda calculus —
Premise If somebody is a wizard,…
Static type checking Predicting that muggles can’t do magic
Turing machine —
Type Spell, wizard, muggle
Type checker The world of magic
Typing rule If somebody is a wizard, he or she can cast spells
Notes
Introduction
1. John Dewey, “The Pattern of Inquiry,” in Logic: Theory of Inquiry (1938).
Chapter 1 A Path to Understanding Computation
1. Quotations are taken from the free online version of Grimms’ Fairy Tales by Jacob Grimm and Wilhelm Grimm that is available at www.gutenberg.org/ebooks/2591.
2. The terminology can get a bit confusing here, since the term problem is generally used for one particular problem instance as well as for a whole problem class. For example, we talk about the “problem of way-finding” in general as well as the concrete “problem of finding a way between two specific locations.” In most cases, however, the ambiguity is resolved by the context.
3. This is true only under certain assumptions that are discussed later.
Chapter 2 Walk the Walk: When Computation Really Happens
1. The amount of ground coffee follows the National Coffee Association’s recommendation; see www.ncausa.org/i4a/pages/index.cfm?pageID=71.
2. The first recorded use of the word computer dates back to 1613. The first idea of a mechanical computer was the Difference Engine, designed by Charles Babbage in 1822. The first programmable computer, the electro-mechanical Z1, was built around 1938 by Konrad Zuse.
3. This assumes that Hansel and Gretel do not take any shortcuts and that they do not have to backtrack to resolve dead ends (see chapter 1).
On Your Way
1. If you have never driven in the United States, Canada, or South Africa, you may not know this traffic rule. For somebody who first learned how to drive in Germany, four-way stop streets are a truly amazing concept, in particular, the fact that they cause so few accidents and quarrels about who came first.
2. This follows, since signs are representations and since we have identified computation as the systematic transformation of representations.
Chapter 3 The Mystery of Signs
1. A binary number is a sequence of 1s and 0s. The first few natural numbers are represented in binary as follows: 0 ↦ 0, 1 ↦ 1, 2 ↦ 10, 3 ↦ 11, 4 ↦ 100, 5 ↦ 101, 6 ↦ 110, 7 ↦ 111, 8 ↦ 1000, 9 ↦ 1001, and so on.
2. If you think this is complicated, consider this. I am writing this chapter in early 2015, and we are close to Superbowl XLIX, which is the Roman way of saying 49. L means 50, placing an X before it means to subtract 10. Now we have to add 9 more, which can be achieved by appending IX, which itself means to subtract 1 from 10.
3. Doubling in the binary system is as easy as multiplying by 10 in the decimal system: simply add a 0 at the right end.
4. In general, the intersection operation can produce multiple points (or no point) in case the road crosses the river more than once (or not at all).
5. The Hound of the Baskervilles does not contain computations with individual symbols; however, it does contain computations with collections of symbols (see chapter 4).
Chapter 4 Detective’s Notebook: Accessory after the Fact
1. Quotes are taken from the free online version of The Hound of the Baskervilles by A. Conan Doyle that is available at www.gutenberg.org/files/2852/2852-h/2852-h.htm.
2. There are more sophisticated versions of lists, for example, lists whose elements are connected in both directions. However, this chapter discusses only the simple singly linked list.
3. In principle, the order of elements could be of importance, and the position in the list could be used, for example, to express the degree of suspiciousness of each member. But in the story there is no indication that Sherlock Holmes maintains such an order.
4. Note that this assumption is generally not justified; it is usually not possible to use names as identifiers for array cells and get efficient access to array cells. This limitation can be overcome, in part, by employing more advanced data structures such as hash tables or so-called tries, which are discussed in chapter 5. We can ignore this limitation in what follows because the comparison of lists and arrays is not affected by it.
5. See wikipedia.org.
6. A wiki is a program for collaboratively editing and sharing information over the internet.
7. Their ultimate goal is, of course, to trim the set down to contain exactly one element.
Lost and Found
1. In case you forgot how to do it, there are numerous instructions to be found on the internet, although finding instructions that are just right for you might again be a difficult search in itself.
Chapter 5 The Search for the Perfect Data Structure
1. See www.youtube.com/yt/press/statistics.html; web site checked on September 16, 2015, see web.archive.org/web/20150916171036/ http://www.youtube.com/yt/press/statistics.html.
2. The inside is not guaranteed to contain the element, since the element we are looking for may not exist at all in the search space.
3. See en.wikipedia.org/wiki/Boggle.
4. This assumes that the tiles do not have to be stepped on in a particular order and that all safe tiles do not have to be visited.
5. Thus, to ensure that each letter of a word is only counted once, we have to maintain a set data type when processing the word. We check that the set does not contain the letter before updating its count, and we add the letter to the set afterwards to prevent further updates to the count from later occurrences in the same word.
6. In fact, it takes time proportional to the number of elements times the logarithm of this number. This time complexity is also called linearithmic.
7. The word was originally pronounced “tree” as in retrieval, from which it was derived, but today many people pronounce it “try” to emphasize the special features that distinguishes it from search trees in general.
8. Half of the nodes in a binary tree are con
tained in its leaves.
Getting Your Ducks in a Row
1. An algorithm has linearithmic runtime if it requires time proportional to the size of the input (here the number of students or exams) times the logarithm of that number.
2. Even taking into account that the list of exams gets shorter in each step.
Chapter 6 Sorting out Sorting
1. More precisely, .
2. Since we have removed the pivot.
3. Referring to logarithms to the base 2. Thus, log2 100 < 7, since 27 = 128, and so on.
4. John von Neumann is probably best known in computer science for describing a computer architecture on which most of the computers existing today are based.
5. This is because between any two names that might be used as adjacent array indices, there exist infinitely many other names. Say you decide that index “aaa” should be followed by “aab”; then indices such as “aaaa,” “aaab,” “aaaaa,” and infinitely many others would not occur as indeces in the array and could not be counted. For the same reason arrays cannot be indexed by real numbers, and therefore counting sort cannot be used for sorting lists of real numbers.
6. Or at least one of the Holy Grails, since there can be multiple optimal algorithms.
7. All possible lists of length n (containing different elements) can be constructed as follows. Any of the n elements can be in the first position. Then any of the remaining n − 1 elements can be in the second position, and so on. Altogether this amounts to n×(n−1)×…×2×1 = n! possibilities, which means that there are n! different lists of length n.
8. An algorithm that uses no more than k comparison operations can distinguish between 2k different cases. Thus to cope with all possibilities for a list of length n, it must be that 2k ≥ n!, or k ≥ log2(n!). One can then show that k ≥ n log2 n, which yields the linearithmic lower bound.
Chapter 7 Mission Intractable
1. This includes the empty combination, which is the solution for the case when the weight should be zero. This case is not important in this example, but it is a possibility in general. Excluding the empty set does not change the fact that the number of possible combinations is exponential in the number of available objects.
2. In fact, Moore’s law, which had its 50-year anniversary in 2015, is coming to an end, since the miniaturization of electronic circuits has reached fundamental limits imposed by physics.
3. A quadratic algorithm for input of size n performs about n2 steps. Doubling the computer’s speed means that it can execute in the same time twice as many steps, that is, 2n2 steps. This is the number of steps that the algorithm takes for input of size , since . In other words, since , the algorithm can process input that is approximately 1.4 times as large.
4. About 30 billion atoms would have to be split to produce the energy needed to light up a 1 watt lamp for 1 second.
5. The P stands for polynomial and refers to the class of problems for which a solution can be constructed by an algorithm whose runtime is proportional to a polynomial such as n2 or n3
The N stands for nondeterministic, and NP refers to the class of problems for which a solution can be constructed by an algorithm with polynomial runtime on a nondeterministic machine, which is a hypothetical machine that can always make a correct guess for each decision needed in the algorithm. For example, we can generate a solution for the weighing problem in linear time if we can correctly guess for each weight whether it is included in the solution. Equivalently, NP refers to the class of problems whose solutions can be verified by an algorithm with polynomial runtime. For example, a proposed solution to the weighing problem can be verified in linear time, since it requires only the summation of the weights and the comparison with the target weight.
6. However, if one has to repeatedly find and remove the smallest element from a list, the sorting-based method becomes more efficient at some point.
7. Consider the first object added. It either weighs more than half of the target weight (which proves the case) or it weighs less than half, which means that we can add the next object, since its added weight (which is less than the first and thus also less than half the target weight) does not exceed the target weight.
Now we can again distinguish two cases. If the two objects together weigh more than half of the target, their weight is less than 50% off the target weight. Otherwise, if they weigh less than half, each object must weigh less than one-fourth of the target, and so does the next object, since it weighs even less and can thus be added. Following this line of reasoning shows that we can continue to add objects at least until we have reached half the target weight. This argument assumes there are enough objects available to reach the target weight, but this assumption is already contained in the assumption that we can find an optimal solution.
Doctor’s Orders
1. Ludwig Wittgenstein, Tractatus Logico-Philosophicus (1921), para 5.6, trans. K. C. Ogden. www.gutenberg.org/files/5740/5740-pdf.pdf
Chapter 8 The Prism of Language
1. The Recording Industry Association of America and the National Endowment for the Arts have listed it as the number one entry on their “Songs of the Century” list.
2. Music by Harold Arlen; lyrics by E. Y. “Yip” Harburg.
3. The objective in the telephone game is to transmit a sentence or phrase from one person to the next through whispering. When played with a large group, after a number of transmissions, the phrase often gets distorted in funny ways.
4. Unfortunately, tablature is ambiguous with regard to the duration of notes and can therefore only effectively be used when the performer knows the piece already.
5. To clearly distinguish nonterminal from terminal symbols, the former are always given by a name with a dotted frame around it, similar to the dotted underlining used to represent parameters in chapter 2. This notation evokes the notion of a placeholder that is to be substituted.
6. To represent n different pitches and m different durations, we need n×m rules. This number can be drastically reduced to about n + m rules by decomposing a note into two nonterminals for pitch and duration plus rules for producing these two aspects independently of one another.
7. Idiomatic expressions are an exception to this rule (see chapter 9).
8. Oops. I forgot the last two words “it doesn’t,” which prevented you from successfully parsing the sentence. In this case, you could probably fix the sentence by adding the missing part, but sentences for which that doesn’t work will be left without meaning—a very frustrating experience for the reader or listener.
Chapter 9 Finding the Right Tone: Sound Meaning
1. More precisely, I should say that each sentence has at most one meaning, since some syntactically correct sentences might lack a meaning, for example, what is the meaning of “The green thought ate.”?
Chapter 10 Weather, Rinse, Repeat
1. A town in India that holds records for the highest annual and monthly amounts of rainfall.
2. Recall that step and condition are nonterminal symbols that stand for actions and conditions. When these nonterminals are replaced by an action and a condition, respectively, this program schema becomes instantiated to a concrete program.
3. This is often attributed to Albert Einstein or Benjamin Franklin, but the authorship is not clear. Early written references can be found in Rita Mae Brown’s 1983 novel Sudden Death and in a 1980 Alcoholics Anonymous pamphlet.
4. Alternatively, you can expand the first step to get up and the second one to take a shower; have breakfast, which leads to the same result.
5. There are some important exceptions. For example, most spreadsheet systems do not have a loop to apply, say, one formula, to a number of values or cells. This is typically accomplished by copying rows and columns in the spreadsheet and is much like the expansion of the loop repeat fold three times into the sequence fold; fold; fold.
6. The condition of a repeat loop is appropriately called a termination condition; the condition of the while l
oop is better called an entry condition.
7. The for loops that can be found in most programming languages actually have the following slightly more general form, which provides the body of the loop with information about the number of iterations that have passed:
for name : = number to number do step
This form introduces a nonterminal name that acts as a counter bound to the current iteration number. It can be used in the body of the loop, as in for n : = 1 to 10 do compute the square of n.
Stop at Nothing
1. Recursion can also be a source of nontermination. However, since any recursive algorithm can be transformed into a nonrecursive one that uses loops, it is sufficient to consider only loops.
Chapter 11 Happy Ending Not Guaranteed
1. Of course, the really important part of the algorithm has been left out. We only assume that the condition that tests termination can be defined in some way, which, as shown later, is actually impossible to do.
2. See en.wikipedia.org/wiki/Barber_paradox.
3. If a problem asks for a yes or no answer, as in the case of the halting problem, it is called a decision problem. A decision problem that has no algorithmic solution is called undecidable; otherwise it is called decidable.
If a problem asks for a specific output value for any given input value, it is called a function problem. A function problem that has no algorithmic solution is called uncomputable; otherwise it is called computable.