Foundations of Computer Science

Welcome

Hello • Manahuu • Olá • Hallo • こんにちは • Sawubona • 안녕하세요 • नमस्ते • Bonjour • مرحبًا • Merhaba • Aloha • Cześć • Mabuhay • سلام • Aaniin • Привет • ᎣᏏᏲ • 你好 • Dia duit!

We humans are intelligent, sentient, conscious, embodied beings. We can know, learn, and communicate. We use language, we process information, and we reason. We would like to know what language, information, and reasoning are, and would like to know how we use language, process information, and reason. A powerful way to answer these questions is to not just study these things via observation, but to build machines that can do these things.

Though these machines cannot live a human life, their ability to use language, process information, and reason at speeds that far exceed our own—and with minimal human intervention—can amplify and augment human capabilities in profound ways. If only there was a field dedicated to understanding these capabilities. Wait. There is.

Computer Science is the study of information, computation, and automation.

What are Foundations?

Every study has organizing principles and foundational concepts that guide its inquiry and methodology. In computer science, these principles and concepts come from work in five areas:

1. Information is that which informs. Or more precisely, the resolution of uncertainty. Information can be stored, transmitted, and processed.
2. Computation is the mechanical generation of new information from old information, where mechanical means “in a sequence of steps that each take a finite amount of time and resources.”
3. Language is used to express and communicate both information and computation.
4. Logic is the study of reasoning and argumentation, providing the rules and principles for valid inference. One of the greatest philosophical discoveries of the 20th century is the equivalence of programs and proofs. Logic and computation are deeply intertwined.
5. Automation is the act of specifying a computation and handing it off to a machine for execution with minimal human intervention. Computing devices which operate in this manner are called automata, and can be physical (hardware) or abstract (software).

When you do work in foundations, you reduce everything to essential principles—sometimes all the way to a single kind of thing from which everything can be built back up.

A benefit of having foundations is that understanding and reasoning becomes easier, since there are fewer concepts to keep track of. Your study becomes far more precise and rigorous. Having foundations puts our entire field on a solid footing, free of contradictions, and ensures that we are not talking nonsense. It allows us to make claims and back them up.

The foundations of a discipline are required for the field to be able to assert its claims accurately and without contradictions.

We’ll now look at the foundations of computer science. Keep in mind that these notes are very introductory! We’re only going to take a brief look at the five areas of study that contribute foundations. Many of these topics will be explored in greater depth later in the course.

Information

Information needs to be encoded, stored, transmitted, and processed. Let’s start by asking how we might encode information.

Here’s a first shot, employing some foundational thinking. A symbol is a primitive unit of information. All information, we’ll postulate, can be represented with strings of symbols. Examples:

91332.3e-81
⚠️ Stay BEHIND the yellow line! ⚠️
<ul><li>你好</li><li>ᎣᏏᏲ</li><li>ᐊᐃᓐᖓᐃ</li></ul>
/Pecs/Los Angeles/Berlin/Madrid//1 2/3 0/2 2/2 0/3 2///
(* (+ 88 3) (- 9 57))
int average(int x, int y) {return (x + y) / 2;}
{"type": "dog", "id": "30025", "name": "Lisichka", "age": 13}
∀α β. α⊥β ⇔ (α•β = 0)
1. f3 e5 2. g4 ♛h4++

Now, where do the symbols come from?

The answer is you get to make them up. This is what it means to be the primitive unit of information.

We are going to explore Unicode. As we do, notice how each of the characters have a name. The name seems to suggest a meaning, but does it really? Do symbols have an inherent meaning? Should they? Or is it acquired somehow? If acquired, how so?

There is an established discipline called Information Theory that we won’t cover in depth here. You can take full-length college courses and read hundreds of books on this topic. It is huge! The genesis of the theory is attributed to Claude Shannon whose 1948 paper A Mathematical Theory of Communication is legendary—perhaps one of the most influential scientific papers of all time. Among the many contributions of the paper, Shannon:

• Identified the fundamental problem of communication, namely “that of reproducing at one point either exactly or approximately a message selected at another point.”
• Defined the participants in a communication system: messages are produced by an information source, and transmitted as (encoded) signals over a possibly noisy channel, and received (decoded) for a destination.
• Showed that statistics was an inherent part of communication: “...significant aspect is that the actual message is one selected from a set of possible messages.”
• Introduced the concept of entropy as a measure of uncertainty in a message. (Low entropy means less uncertainty and therefore requires fewer bits to describe; high entropy means more uncertainty and therefore requires more bits to describe.) Entropy is incredibly important in communication, cybersecurity, data compression, machine learning, and many other fields.
• Noted that logarithmic functions are good (perhaps the best) measures of information: a device with two stable states can hold one bit of information; a device with four stable states can hold two bits of information; a device with 10 stable states can hold one decimal digit of information, and so on. (For a readable explanation of why logs work so well, see this primer.)

Information Theory is used in the foundations of computer science for encoding data, ensuring reliable communication, optimizing and securing storage and transmission, and building machine learning models and systems.

Computation

Computation is the processing of information.

The human understanding of, and application of, computing has evolved over millennia. It has arguably enhanced human capabilities. To study what it is and how we do it, we must look at its history. History is an essential component of the study of any discipline and empowering to know. However:

[Computing is] complete pop culture. The big problem ... [is that] the electronic media we have is so much better suited for transmitting pop-culture content than it is for high-culture content. I consider jazz to be a developed part of high culture. [Jazz aficionados take deep pleasure in knowing the history of jazz, but] pop culture holds a disdain for history. Pop culture is all about identity and feeling like you're participating. It has nothing to do with cooperation, the past, or the future—it's living in the present. I think the same is true of most people who write code for money. They have no idea where [their culture came from]. —Alan Kay

Woah. He’s right. Let’s do something about this.

For thousands of years, humans have been marking, matching, comparing, tallying, measuring, and reckoning. The Ishango bone, from around 20K years ago, was likely used for such purposes.

Tallying was aided by pictorial markings like 🌽🌽🌽🌽🌽 🍓🍓🍓. Then someone figured out they could save space by writing something like 5🌽 3🍓. An incredibly powerful idea: symbols representing quantities—the mighty numeral:

Early numeral systems like the Egyptian system were additive, but in the modern era, positional systems have become universal.

Numerals enabled a powerful advance in human capabilities: recipes, or lists of instructions, for manipulating quantities and measurements could now be recorded. Notable examples include:

• Babylonian Tablets 1800-1600 BC
• Rhind Mathematical Papyrus (~1550 BC)
• Euclid’s greatest common divisor method (~300 BC)
• Eratosthenes method for enumerating primes (~240 BC)
• Muḥammad ibn Mūsā al-Khwārizmī’s Al-Jabr (813-833), which included systematic solutions for linear and quadratic equations

The term algorithm meaning a description of a computation comes from Al-Khwārizmī. People happily used computations for over a thousand years without a formal definition of what an algorithm actually was. To be fair, no one really needed one. But the need for such a definition did arise. In the 19th century, philosophers and mathematicians started making some major advances in their fields, breaking free of Aristotlean syllogistic thinking. Major works of this era include:

• Boole’s Boolean Algebra (1847)
• Frege’s Begriffsschrift (1879)
• Peano’s Axioms (1889)
• Hilbert’s Program (early 1920s)
• Russell and Whitehead’s Principia Mathematica (1910–1913)

During this era, people started noticing inconsistencies and paradoxes popping up in mathematics, and started an effort to get mathematics on a solid foundation. This ultimately led to David Hilbert challenging mathematicians to show that all of mathematics could be built from an axiomatic formal system that was sound (everything derivable is true), complete (every truth is derivable), consistent (no contradictions can be derived), and decidable (an algorithm exists to determine a priori whether a statement could be derived in the system).

But it was not to be.

Kurt Gödel, in 1931, proved that any attempt at providing a consistent, formal, axiomatic basis for mathematics (that included arithmetic with multiplication) could never capture all truths. Formalized mathematics had, then, to be incomplete (or inconsistent, but that’s unacceptable). Gödel did not answer the decidability question, or Entscheidungsproblem. Hilbert thought mathetmatics was decidable, that a decision procedure for all of mathematics existed. Others did not. But to prove him wrong, a formalization of the very notion of an algorithm is required. Three attempts were made in the 1930s (all successful by the way):

• Church’s Lambda Calculus
• The μ-recursive Functions (mostly worked out by Gödel, Kleene, and others)
• Turing Machines

Church and Turing both succeeded in showing the Entscheidungsproblem had no solution. That is, no such algorithm existed. Poor Hilbert.

Story Time

We‘ll go over the story of Church, Gödel, and Turing in class only. You can’t find everything on the notes!

Turing’s work is particularly notable, and his 1936 paper is one of the most impactful and significant of all time. In this work:

• He gave a formalization of effective computation (algorithms) that people could actually understand—significant because previous models were extremely dense (Church’s) or reliant on advanced mathematics (Gödel’s).
• He gave evidence as to why his formalization, now called the Turing Machine, coincides with our intuitive notion of “computable” (the Church-Turing Thesis).
• He introduced computational universality: programs were just data (ok so far, not surprising) and, wait for it, a single machine could emulate, or “run,” any other machine ‼️🤯😮😳🤩. Before this work, it was not known (but it may have been suspected by some) that a truly universal computer could exist—separate machines were thought to be necessary for different tasks.
• He showed that some numbers were not computable, some functions were not computable, and that some questions could not be mechanically decided—and hence, that the Entscheidungsproblem had no solution—a result shocking to many (but not all) mathematicians of the era.

Turing is revered as the founder of computer science because of this work. The ideas that there are limits to computation, equivalent ways to express computation, and the existence of a truly universal computing machine make computer science a discipline.

If you’d like to explore the discovery of the limits of formalized mathematics and how they were demonstrated by Gödel and Turing, here’s a long-form video with a disgusting and misleading click-baity title (incompleteness is a feature, not a flaw):

In case your only previous exposure to Turing was the movie The Imitation Game, remember that movies aren’t history. They make stuff up that never happened and they modify real events for dramatic effect. Here’s a brief video pointing out a few inaccuracies of the movie, some rather insulting to Turing himself, and to his many collaborators:

Automation

Humans can compute, unassisted, by following recipes and carrying out reckoning with their fingers and toes, or using tally marks on bones. But assistance is good, so machines were invented to help with these tasks, such as the Abacus (earliest known from Sumeria 2700–2300 BC) and the Slide Rule (1620s). But with these machines, a human had to guide every step of the process. The machine was just a tool, not an agent. These are cool things, but not computer science.

You know what’s coming next. Humans did indeed create devices that can process complex information automatically, once an initial input is given, including:

• Astrolabe (~200 BC)
• Antikythera mechanism (~200 BC)
• Pascal’s calculators (1640s)
• Jacquard Loom (1804)
• Babbage’s Difference Engine (1820s) and Analytical Engine (1837)
• Hollerith’s Tabulating Machine (1880s)

The Jacquard Loom and Analytic Engine were rather unique as they were programmable. This is next-level automation.

The Analytical Engine was fascinating historically. Although never built, it was perhaps the world’s first programmable, general-purpose computer. Several programs are known to have been written for the device, the most famous of which—a program for the computation of Bernoulli numbers—was presented by Babbage’s collaborator Ada Lovelace in her translator’s notes to Luigi Menabrea’s article in Taylor’s Scientific Memoirs in 1843. (Also see this shorter summary). Lovelace is often considered the world’s first programmer. She is also widely admired as being perhaps the first to recognize the wide application of computing beyond arithmetic, writing that the Analytic Engine

might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine.... Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.

But it took a long time from Babbage to the next big step in automation. It was Turing's Universal Machine from his famous paper—a completely abstract but completely specified paper design—that opened up a flood of new work in general purpose machines. Wikipedia’s History of Computing Hardware page covers both ancient devices and a fair number of machines from the 1930s–1960s. It is worth a look to see how we eventually got to the electronic devices that are ubiquitous today.

Now we had powerful machines that operated quickly but getting the instructions into the machine was slow, laborious, and error-prone. Even moving from wires to stored-program architectures did not help too much. What was needed was a deeper understanding of language to describe computation.

Language

There are many ways to describe what we mean by the word language. Here’s just one of many: In a TPWKY podcast appearance, Steven Mithen, author of The Language Puzzle, describes language as a system of communication comprised of discrete units with shared, often arbitrary meanings, combined using specific rules to generate and interpret complex thoughts.

Language can be studied from multiple perspectives, three of which are:

Computer Science foundations tends to focus on the first of these perspectives, but in order to even know where to start in formulating foundations, one must begin with a study of the many diverse ways that language is used and how information and computations are expressed today. We saw a diverse set of human language greetings at the top of this page, now here’s a look at diverse ways to represent a simple computation: summing the squares of even numbers from a collection:

One approach is to explicitly iterate through the list, checking each element to see if it is even, and if so, squaring it and accumulating the square into the final answer. This is the approach we must take in Go:

func sumOfEvenSquares(a []int) int {
    total := 0
    for _, x := range a {
        if x % 2 == 0 {
            total += x * x
        }
    }
    return total
}

Another approach is to first filter (a.k.a. ”select”) the even numbers, then map the squaring operation over each of them, and finally reduce (a.k.a. “fold”) the plus operation over the filtered-and-squared values to produce the result. For example:

• Input List: [3, -2, 9, 51, 20, 8, 0, -31, 10]
• After filtering by (keeping) evens: [-2, 20, 8, 0, 10]
• After mapping the square function: [4, 400, 64, 0, 100]
• After reducing the sum function: 568

Most major programming languages have these operations built-in. TypeScript and Java are two of them:

function sumOfEvenSquares(a: number[]): number {
  return a.filter(x => x % 2 === 0).map(x => x ** 2).reduce((x, y) => x + y, 0)
}

int sumOfEvenSquares(int[] a) {
    return IntStream.of(a).filter(x -> x % 2 == 0).map(x -> x * x).sum();
}

Sometimes you can specify the filtering, mapping, and reducing functions without parameters, as in Haskell and Factor:

sumOfEvenSquares :: [Int] -> Int
sumOfEvenSquares = sum . map (^ 2) . filter even

: sum-of-even-squares ( seq -- n )
    [ even? ] filter [ sq ] map sum ;

Sometimes the filtering and mapping can be expressed in a single construct, as in Python::

def sum_of_even_squares(a):
    return sum(x**2 for x in a if x % 2 == 0)

And then there are languages with really, really powerful operators for processing arrays, as we see in K and Julia:

sumofevensquares: {+/x[&~x!2]^2}

function sumOfEvenSquares(a)
  sum((a[a .% 2 .== 0]).^2)
end

Getting to high-level languages was frankly pretty incredible. Assembly language (co-invented by Kathleen Booth) was a powerful step. John von Neumann seemed to try to block it, once angrily asking “Why would you ever want more than machine language?”. But there was no stopping the advances in language. One of the biggest proponents of high-level languages was Grace Hopper, who also happened to write the first compiler.

Languages have to not only be expressive, but they have to be efficiently implementable. This is why we study compilers and interpreters. Two major parts of this field are:

• Formal Language Theories (from Chomsky and others) that enable parsing to be efficient
• Optimizations (Frances Allen was a major figure in this area)

Expressing computing with language, either of the programming variety or natural language, has enabled human-centric computing. People create programs for people. Areas with people-focus include:

• Graphics and user interfaces
• Computing in education
• Libraries for creative computing

The study of how humans use their natural languages and invent languages for expressing concise computations is the starting point for coming up with foundations of language itself. The study of both human and computer languages have led to the invention and discovery of such concepts as alphabets, vocabularies, words, morphemes, symbols, grammar, syntax, semantics, neural networks, backpropagation, attention, transformers, and more.

Language Theory is used in the foundations of computer science to rigorously and unambiguously specify the structure and meaning of programming languages and computational systems.

Logic

Logic is the study of reasoning.

When we reason, we move from information (premises) to new information (conclusions) using rules of inference. Reasoning, or argumentation, is made by apply rules to judgments. As a field, logic studies not just specific arguments, but the general forms of arguments. Here’s a simple example:

Logic and computation are inseparable. Deriving new information via logical inference is equivalent to deriving new information through computation. The Curry-Howard Correspondence, one of the great 20th century discoveries, clarifies a beautiful isomorphism:

Propositions as Types

Proofs as Programs

As a sneak peak, note the correspondence between function application (from computation) and the inference rule of modus ponens (from logic):

Logic has been studied for thousands of years. Much of it can be mechanized; indeed, so much new mathematics today is done via complex machine-assisted proofs. Generative AI has led to systems that can discover new proofs on their own. We can learn much about computation and automation by looking at the history of logic and its major results.

Application of Foundations

Knowledge of foundations gives one the required knowledge and skills essential for advancing any field. Notable advances in computer science have all used foundational principles. These include:

• Personal computers (1970s)
• Internet (1980s)
• Web (1990s)
• Mobile (2000s)
• Cloud (2010s)
• Generative AI (2020s)
• Quantum Computing (?)

You will have noted the foundations of computer science are greatly influenced by Philosophy, Linguistics. Mathematics, Engineering, and other disciplines. There’s something interesting about the field. Grady Booch’s Computing: The Human Experience project has this to say:

The story of computing is the story of humanity: this is a story of ambition, invention, creativity, vision, avarice, power, and serendipity, powered by a refusal to accept the limits of our bodies and our minds. Computing: The Human Experience is a transmedia project that explores the science of computing, examines the connections among computing, individuals, society, and nations, and by considering the history of computing contemplates the forces that will shape its future.

The story of computing is “powered by a refusal to accept the limits of our bodies and our minds”

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What does sawubona mean?
   It is a Zulu greeting that means "I see you"—a bit more that just a simple hello, as it signifies respect for, validation of, and the presence of the (whole) person you are acknowledging.
2. What is computer science the study of?
   Information, computation, and automation.
3. Why does a discipline need foundations?
   For the field to be able to assert its claims accurately and without contradictions.
4. What does the study of foundations enable?
   A deeper understanding of the field and the ability to make advances in the field.
5. What five areas are foundational to computer science?
   Information, computation, automation, language, and logic.
6. What is information?
   Information is that which informs. Information is the resolution of uncertainty.
7. Who is credited with launching Information Theory?
   Claude Shannon
8. What kind of measures are used for information?
   Logarithmic ones.
9. What is a symbol?
   A primitive unit of information.
10. What is Unicode?
    Unicode is a standardized system for encoding, representing, and handling text expressed in most of the world's writing systems.
11. What is computation?
    The formal, mechanical, generation of new information from old information.
12. According to Alan Kay, why is computing history not widely known?
    Because pop culture, which computing arguably is, holds a disdain for history.
13. What is the significance of numerals?
    They allow large quantities to be expressed with fewer symbols.
14. Show how to represent the quantity twenty-one thousand two hundred thirty-seven using Egyptian Numerals:

    

15. What are some ancient media on which early recipes for calculation were recorded?
    Babylonian Tablets and the Rhind Mathematical Papyrus.
16. What are some early famous nontrivial algorithms?
    Euclid’s greatest common divisor method and Eratosthenes method for enumerating primes
17. From whose name do we get the word “algorithm” from?
    Muḥammad ibn Mūsā al-Khwārizmī
18. What were some of the accomplishments of Al-Khwārizmī?
    He wrote Al-Jabr, which included systematic solutions for linear and quadratic equations.
19. Where and when were abaci first known to be used?
    Sumeria 2700–2300 BC.
20. What could the Antikythera mechanism do?
    It was an analog computer that could predict astronomical positions and eclipses.
21. Babbage is known for designing two machines. Which ones?
    The Difference Engine and the Analytical Engine.
22. Was the analytical engine ever built?
    No.
23. What was Ada Lovelace’s published program in her famous Notes?
    A program for the computation of Bernoulli numbers.
24. What was Lovelace most known for besides the first published program?
    She was arguably the first to recognize and to write about the wide application of computing beyond arithmetic.
25. What are the three major philosophies about what math is?
    Logicism, Formalism, and Intuitionism.
26. Who is the guy most associated with the formalist movement in mathematics, so much so that he felt formal systems could capture all of mathematics through proof and computation?
    David Hilbert.
27. What was Hilbert’s Program?
    A call to people of his time to formalize all of mathematics.
28. What did George Boole introduce to the world?
    Boolean Algebra.
29. What did the logicists think math was? What did the formalists think it was? The intuitionists?
    Logicists: a branch of logic. Formalists: a game of manipulating symbols according to rules. Intuitionists: an invention for constructing objects and facts about them.
30. What was the Entscheidungsproblem?
    Hilbert’s question of whether there was an effective, finite, decision procedure for all statements of mathematics.
31. What were the three major attempts at formalizing computation in the 1930s?
    • Alonzo Church’s Lambda Calculus
    • Kurt Gödel’s Mu-Recursive Functions
    • Alan Turing’s Turing Machines
32. How did Church formalize the notion of effective computability?
    With the Lambda Calculus.
33. How did Turing formalize the notion of effective computability?
    With the Turing Machine.
34. What was Gödel's initial reaction to Church’s Lambda Calculus, and what did this reaction motivate Gödel to do?
    He was skeptical that the Lambda Calculus was a model for effective computability (because it was so simple), so he created his own model, the μ-recursive functions.
35. After Church demonstrated the equivalence of the Lambda Calculus and the μ-recursive functions, what was Gödel’s reaction?
    He thought his own model, the μ-recursive functions, must be insufficient.
36. When did Gödel finally accept the Lambda Calculus a model for effective computability?
    After Turing showed that the Lambda Calculus and Turing Machines were equivalent. All agreed that Turing machines were a sufficient model, thus the other two approaches must also be.
37. Name four stunning achievements of Turing’s famous paper.
    Turing (1) gave a formalization of effective computation, (2) showed that his formalization coincided with our intuitive notion of “computable”, (3) introduced computational universality, and (4) showed that some numbers (and by extension some functions) were not computable.
38. Why was the ENIAC famous?
    It was the first general-purpose electronic computer.
39. Who were the ENIAC six?
    Kay McNulty, Jean Bartik, Betty Holberton, Marlyn Meltzer, Francs Spence, and Ruth Ruth Teitelbaum.
40. What are three ways of looking at language?
    (1) As mathematics, (2) as biology, archaeology, and culture, and (3) as statistics and engineering.
41. What is a programming language?
    A language for expressing computations.
42. Who wrote the first compiler and what was it called?
    Grace Hopper. The A-0 System.
43. Why are programming languages important?
    They enable the expression of computation at such a high level that creative and impactful computing become accessible to the masses.
44. Why is LISP so loved?
    Simple syntax and semantics, homoiconicity, macros.
45. Why is Ruby so loved?
    It is extremely expressive, allows for rapid development, and has excellent metaprogramming facilities.
46. Why is CLU so significant?
    It introduced data abstraction, iterators, and exception handling.
47. What else is Barbara Liskov known for besides designing CLU?
    She introduced the Liskov Substitution Principle.
48. What was Noam Chomsky’s biggest contribution to computer science?
    He introduced the Chomsky Hierarchy, which served as a foundation for modern parsing theory.
49. What is Frances Allen known for?
    She was a (if not the) major figure in the field of compiler optimization. It is said that among all the optimizations performed in modern compilers, she probably came up with or at least described 80% or more of the most important ones.
50. What year did Allen win the Turing Award?
    2006.
51. What even is Generative AI?
    AI that can create new things, like images, music, code, or text.
52. What is logic?
    The study of reasoning.
53. What is the Curry-Howard Correspondence?
    The deep and often surprising relationship between computer programs and mathematical proofs, often phrased as “propositions as types” and “proofs as programs”.

Summary