Theories in Computer Science

What is a Theory?

We’ll begin with this definition from an actual respected dictionary:

theory (n.)

1. A set of statements or principles devised to explain a group of facts or phenomena, especially one that has been repeatedly tested or is widely accepted and can be used to make predictions about natural phenomena.
2. The branch of a science or art consisting of its explanatory statements, accepted principles, and methods of analysis.

Sure, sometimes folks use the word “theory” for a hunch or a supposition, but in the arts and sciences, a theory is an organized body of knowledge with explanatory and predictive powers.

A theory is an organized body of knowledge with explanatory and predictive powers.

Why Study Theory?

We build a theory to organize our knowledge and develop a vocabulary that we can use to reason about things, communicate with others, make predictions, and generate new knowledge.

Without a theory, we can still do things, but not as well: there’s a lot of improvisation, difficulty in communicating ideas, guess work, and flailing around. Your practice will not be as strong, and your insights may be limited. Let’s see how David Bennett expertly makes this point. The key ideas are expressed from 17:21-18:42 (though the whole video is interesting):

Music theory can be helpful in creating music, but can it help us enjoy music more? Certainly! After all, theoretical knowledge adds to our awe of that which we study, allowing us to appreciate the beauty of something at more than just one level:

Theories of Computation

The field we now call Computer Science has a long and fascinating history. Several theories emerged as the discipline took shape. A computer scientist has a working knowledge of these theories and employs them to not only create useful applications and systems, but to advance the state of the art. There are four major theories under the umbrella term “The Theory of Computation.” Two are rather fundamental:

The third and fourth get into certain specifics but have deep and fascinating philosophical roots:

To study and apply these theories, we need some context.

Computation augments and amplifies human thought. Modern computers speed up time to such an extent that our reasoning powers are at a qualitatively different level than what we had before these machines. These computational theories help us qualify and quantify how exactly this augmentation occurs. They enable us to ask and answer questions such as

• What even is computation?
• What can and cannot be known through computation?
• What can and cannot even be computed?
• What can and cannot be computed under certain time and space constraints?

In order to be accepted and useful, these theories must be grounded with practical axioms that match our intuition of what computations actually are. We will take as given that a computer is a finite device and a program is a finite set of instructions.

Also...

The areas of computer science in which theory is most directly applied are often the most interesting, important, and the most lucrative for practitioners. These include cybersecurity (esp. cryptology), AI, (esp. machine learning), advanced data structures such as those powering blockchains, distributed computing, and novel hardware architectures.

Language Theory

Language Theory is concerned with how information and computation are expressed. It begins with the question “What is information?” and approaches the question with the hypothesis that any piece of (human-usable) information can be represented as a string of symbols. To see why this hypothesis is useful, note these examples:

• 91772.3e-8
• Stay behind the yellow line!
• ᐊᐃᖓᐃ ᓄᓇᕐᔪᐊᖅ
• /Pecs/Los Angeles/Berlin/Madrid//1 2/3 0/2 2/2 0/3 2///
• (* (+ 4 3) (- 9 7))
• int average(int x, int y) {return (x + y) / 2;}
• <dog id="30024"><name>Lisichka</name><age>13</age></dog>
• {"type": "dog", "id": "30024", "name": "Lisichka", "age": 13}
• ∀α β. α⊥β ⇔ (α•β = 0)
• 1. f3 e5 2. g4 ♛h4++

Symbols are chosen from some finite alphabet, such as $\{0,1,2,3,4,5,6,7,8,9\}$ for the language of natural numbers, or $\{0,1,2,3,4,5,6,7,8,9,.,\textrm{e},\textrm{E},+,-\}$ for the language of floating-point numbers. What is a language? A language (in Formal Language Theory) is a set of strings over an alphabet; that is, some strings are in-the-language and some are not. For example, in the language-of-floating-point-numbers, 3.55E+21 is in the language, but +-9-E...2 is not. Beyond formal language theory, we consider a language to also contain an assignment of “meaning” to each string in the language.

Here’s an obvious, but important, point worth stating: strings in a language represent not only numbers, text, and complex data structures, but also abstractions of computations known as functions, which produce output information from input information. Examples:

• double, which takes a number and returns twice that number, e.g., double(3.5) $\Longrightarrow$ 7
• plus, which takes a pair of numbers and returns their sum, e.g., plus(4, -3) $\Longrightarrow$ 1
• nextMove, which takes a game state and returns the next (best?) move that should be made
• upperCase, which takes a piece of text and returns a string like it in every way except all letters are in upper case, e.g., upperCase("Please don’t shout!") $\Longrightarrow$ "PLEASE DON’T SHOUT!"
• sorted, which takes a list of things and returns a new list containing the same values in sorted order, e.g., sorted([4, 7, 1]) $\Longrightarrow$ [1, 4, 7]
• even, which takes a number and returns true or false depending on whether the number is even, e.g., even(797) $\Longrightarrow$ false
• twice, which takes a function and a value and applies the function to the result of applying the function to the value, e.g., twice(double, 5) $\Longrightarrow$ double(double(5)) $\Longrightarrow$ double(10) $\Longrightarrow$ 20
• javac, which takes a string in the Java programming language and returns an executable class file
• java, which takes a class file and returns (the effect of) its execution
• python, which takes a string in the Python programming language and returns (the effect of) its execution, e.g., python("print(8 * 5 - 2 / 1)") $\Longrightarrow$ {stdout: "38"}

But how to we express computations? We can design languages to do this. We can make practical languages, or we can try to see how primitive we can make them. Alonzo Church invented the Lambda Calculus to show that function definition and application could serve as a foundation for mathematics. Here are example functions:

• λx. not (equal (mod x 2) 0)
• λp. λn. λr. λt. times p (power (plus 1 (divide r n)) (times n t))

Surface-level abbreviations (syntactic sugar) are okay:

• $\lambda x\,.\,x\:\textrm{mod}\:2 \neq 0$
• $\lambda (p,n,r,t)\,.\,p \times (1 + \frac{r}{n})^{nt}$

To make things even more practical, real programming languages have been created. Here’s the “is even” computation expressed in a few:

• (LAMBDA (x) (NOT (EQUAL (MOD x 2) 0)))   (Lisp)
• lambda x: x % 2 != 0   (Python)
• x => x % 2 != 0   (JavaScript)
• (x) -> x % 2 != 0   (Java)
• ->(x) {x % 2 != 0}   (Ruby)
• #(not= (mod % 2) 0)   (Clojure)
• {$0 % 2 != 0}   (Swift)
• |x| { x % 2 != 0 }   (Rust)

In Language Theory, particularly in Programming Language Theory, we study computation expression, as well as the data upon which they operate, and the modules, objects, and control structures which house these functions. We study how syntax definitions can be written to define which strings belong to the language, and how semantic definitions can give meaning to these strings. We even study how these languages are used by human beings, something we call pragmatics. But how can we actually compute (or “carry out”, or “evaluate”) these functions? For that we turn to automata theory.

Automata Theory

In Automata Theory, we build and study formal models of computational devices (i.e., computers). Historically, the theory evolved by first examining computing devices through history, then coming up with primitive actions that could capture any kind of computation.

Early Computing Machines

People have designed or built calculating machines for centuries. Notable examples include:

• Abacus
• Antikythera
• Astrolabe
• Pascal’s adder
• Babbage’s Analytical Engine
• Jacquard’s Loom
• and more

“Babbage never foresaw the terrible consequences of his invention—a machine that would autocorrect his name to ‘cabbage’ every single time.” —Philomena Cunk

These were all amazing feats of engineering and human ingenuity in their own right, but Turing was one of the first to capture the essence of computation in a theoretical computing device.

Turing Machines

When Turing was in his early 20s, he set out to prove that no effective procedure could decide any arbitrary formal statement of mathematics. To do so, he needed to define, formally, what was meant by computation, so he created a simple machine model, or automaton, to precisely capture the very notion of computation. He called machines derived from this model a-machines, but we know them today as Turing Machines. Turing Machines are by no means the only kind of automaton that can carry out computations, but they are special, for a variety of reasons.

Turing set out to formalize what (human) computers did: they followed a set of instructions in which they examined some portion of their paper worksheet, wrote something down or erased something, then moved somewhere else or finished with their result. The actual instructions were based on the human’s state of mind and what was already on the paper. He realized the contents of a two-dimensional sheet of paper could be just as easily represented as a one-dimensional sequence of symbols. So he then reduced the idea to a machine operating on an unbounded sequential paper tape with a read-write head initially pointing to the leftmost symbol of the input. At each step, the machine reads the current symbol, and depending on its current state, (1) optionally rewrites it with a different symbol, (2) optionally moves one square to the left or right, and (3) optionally enters a new state.

Turing’s Story

History is important in understanding just about anything. The story of what motivated Turing to work on the foundations of computing and how he arrived at these fascinating machines, and his brilliant insights into the nature of computation are told very well in the book Turing's Vision: The Birth of Computer Science

That book is well worth a read.

Let’s see a concrete example. Let’s multiply (a binary numeral) by four. How? We just append two zeros to the end of the input! But how can we describe these steps more rigorously with a Turing Machine? Like this:

• Begin in the Scanning state, where our job is to look for the end of the input. In this state, we keep moving right until we encounter our first blank, which we replace with a 0 then move right, entering the Doubled state.
• In the Doubled state, we replace the blank with our second zero, entering the Quadrupled state, from which there is no way out, so that’s where we finish.

Here is how our machine operates with the number five (binary 0101) initially on the tape (And oh, following convention, we use # for blank squares, just because it is easier to see!):

Nice! 5 × 4 is indeed 20 (binary 010100). Now let’s capture the multiply-by-four machine in all its glorious generality:

This says: starting in the Scanning state, while you see a 0 or 1, just move right, but if you see a blank, replace with a 0, move right, and go to the Doubled state. In this state, if you see a blank, replace with a 0 and go to the Quadrupled state. There is no place to go from here, so we’re done.

We can give a pictorial representation of the TM program as a state diagram:

We will generate Turing Machines to (a) floor-divide by four, (b) increment a binary number by 1, (c) compute the two’s complement of a binary number, and (d) compute the value of a binary number modulo 2.

Turing Machines are way too primitive to use for programming efficiently, but their very primitive nature makes them useful to study the nature of computation. We’ll be looking at:

• How Turing Machines that output boolean results are essentially language recognizers, so there is this fascinating connection between language theory and automata theory.
• How Turing Machines can be encoded as strings, and therefore be processed by other Turing Machines.
• The existence of a particular Turing Machine, called the Universal Turing Machine $U$, that, when run starting with the encoding of a machine $M$ and a string $w$ on its tape, will compute exactly what $M$ would compute with input $w$!
• How Turing Machines serve as a basis for studying computability and complexity theory.

Other Kinds of Automata

Turing Machines are not the only model of what we think of as computation (though they might be the most famous). Other models that have been created include:

• Register Machines
• The Lambda Calculus
• Post Systems
• Partial Recursive Functions
• Analytic Grammars
• Queue Automata
• Stack Automata
• String Rewriting Systems
• Cellular Automata

Some have equivalent “computability and recognition power” as Turing Machines, while others do not. But none have greater computing power! But wait, why not? That’s the domain of our next theory—computability theory.

Computability Theory

Now for our next philosophical question. Can every function be represented as a string of symbols that we can process with a machine? In other words, is there a program for every function?

It turns out that the answer is no.

Why?

Programs are just strings, so we can list them in increasing alphabetic order. Programs can be thought of as representing functions in $\mathbb{N} \rightarrow \mathbb{N}$ (since all data can be encoded in binary). Call the enumeration $f_0, f_1, f_2, \ldots$. But $\lambda n. f_n(n)+1$ isn’t in the list! Bottom line:

There exist functions that cannot be computed by any computing machine.

Hey, this is philosophically interesting.

This explanation of why non-computable functions exist was given rather nonchalantly. Did it make sense? It might not have right away because it is an instance of a very powerful proof technique called diagonalization which was at first somewhat controversial. Carry out this proof by sketching the hypothetical list of all functions as a matrix: each row is a function and each column is the argument, and each cell is the result of applying the function (row) to the argument (column). Look at how $\lambda n. f_n(n)+1$ is generated. Do you see why the technique is called diagonalization? Do you see why it works? 🤯

So which functions can be computed? People have, over the years, created many models of computation—the Lambda Calculus, Post Production Systems, Phrase Structure Grammars, Partial Recursive Functions, Random Access Machines, and more. But get this: all have turned out to be equal in power, in terms of what they can compute, to the Turing machine! Even enhancing the basic Turing Machine design with non-determinism or even multiple tapes won’t increase its computing power. These facts suggest the class of computable functions is fundamental. The Church-Turing Thesis claims that what we intuitively understand as “the computable functions” are precisely those for which a Turing Machine can be given, i.e.,

A function $f$ is computable if and only if there exists a Turing Machine that outputs $f(x)$ when started on input $x$.

Remember that Universal Turing Machine briefly mentioned above? It is “universal” because it can simulate any Turing Machine. If the Church-Turing Thesis is true, it’s really universal: it can compute any computable function.

Computability Theory is concerned with figuring out which functions are and are not computable.

Turing Complete

Any computational model that can simulate a Turing Machine is called Turing Complete. Being Turing-Complete is a badge of honor—it means your model can compute anything that is computable.

Read more at Wikipedia. For a technical overview of Turing-Complete models, see Wolfgang Schreiner’s presentation

How about an example? We’ll use JavaScript rather than TMs to simplify the explanation. Let’s write a function called halts that will determine if a function halts on a given input. So we would like:

  halts(Math.sqrt, 100)                ⟶ true
  halts(x => {while (x) {}}, true)     ⟶ false

The idea is simple. Just analyze the input and see if it will halt. But it turns out to be logically impossible to write this function. Why? Assume you can write it. Then consider:

function fox(f) {
  if halts(f, f) while (true) {}
}

Now consider the expression halts(fox, fox). Really consider it. Work it out. See what it is saying. Got it? Woah. We have an antinomy. The assumption you could write halts leads to a contradiction, so you can not write this function to work for all inputs. Interestingly, you can write:

function halts(f, x) {
  f(x);
  return true;
}

So if f(x) halts, you’ll eventually know it, but if it doesn’t, we may never know.

Complexity Theory

Computability theory gives us theoretical limits on what can and cannot be computed, but doesn’t tell us what is practically computable. (A problem requiring $2^{100}$ years to complete is not worth running.) The question “What resources are required to perform certain computations?” or in other words “How much time and memory is needed to solve this problem?” give rise to Complexity Theory.

Complexity Theory gives us results such as “This function requires ________________ to compute”:

• only a single step
• only a fixed number of steps
• logarithmic time
• linear time
• quadratic time
• polynomial time
• exponential time
• no more than a single cell of scratch memory
• scratch memory in the form of a stack (which is very efficient)
• no additional space, or a fixed amount of space
• logarithmic space
• linear space
• polynomial space
• exponential space

Here time refers to the number of basic steps a computation takes on a Turing Machine as a function of the size of the input, while space refers to the amount of memory used during the computation not counting the input itself.

It gets (massively) more interesting, because the theory deals with time and space performance on non-deterministic machines, and parallel machines, and interactive machines, and quantum computers, too. It even considers probabilistic algorithms. Interested? Check out the amazing Complexity Zoo.

Complexity Theory has philosophical as well as practical use. Make sure you are familiar with one of the most famous open questions in all of complexity theory, and perhaps even all of computer science, namely: Does $P = NP$? (Solve it and you will win a million dollars!)

Here’s another great explainer:

There is so, so, much information out there about the P vs. NP question as it really seems to captivate the public.

Working With These Theories

We’ve only briefly introduced the major concerns of four computer science theories without any real depth (or breadth). We’ll have a chance to see each theory in more detail later, covering aspects such as:

• Formal, mathematical, definitions of languages (via grammars) and automata
• Restricted grammars and automata that capture specific kinds of computation
• Language hierarchies capturing both computability and complexity concerns
• Models of computation other than the Turing Machine
• More examples of non-computable functions (beyond the “Halting Problem” we saw above)
• How to construct a Universal Turing Machine
• Examples of languages in many of the common complexity classes
• How to determine the complexity of a problem
• How to create grammars for realistic programming languages
• Why non-trivial programming languages require both a static and dynamic semantics
• Extending these ideas into the much larger Programming Language Theory (PLT)
• How to run a program given its source code (interpret)
• How to translate one programming language into another (compile)

Theories and Creativity, Again

In much the same way that Bennett pointed out that music theory can expand your abilities in music composition, and Feynman spoke of theoretical knowledge in science only expanding and enhancing the feelings of awe and beauty when contemplating nature, might computer science theory enhance one’s imagination for creating new worlds that Booch talks about here?

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 exactly is a theory, in the context of art and science?
   An organized body of knowledge with explanatory and predictive powers.
2. Why are theories important?
   They provide us with a vocabulary to communicate ideas, test hypotheses, and generate new knowledge.
3. What are the four major computation theories and what are they concerned with?
   1. Language Theory: expressing computations
   2. Automata Theory: carrying out computations
   3. Computability Theory: What can and cannot be computed?
   4. Complexity Theory: Resources required for certain computations
4. What is a language, in formal language theory?
   A set of strings over some finite alphabet.
5. What is the lambda calculus concerned with representing and manipulating?
   Functions
6. How do you represent a function to compute the cube of an integer?
   λx. (power x 3)
7. Who came up with the idea of formalizing computing via the Lambda Calculus?
   Alonzo Church
8. Who came up with the idea of formalizing computing via the Turing Machine?
   Alan Turing
9. What was Turing trying to do when he realized he would have to do no less than formally define the very notion of an algorithm (or computational process)?
   He was trying to show Hilbert’s Entscheidungsproblem did not have a solution
10. On what did Turing more-or-less base his fundamental idea of how a formal (abstract mechanical) computing device should work?
    (Human) computers, calculating on paper by moving through mental states looking at symbols, adding new symbols, and erasing existing ones.
11. Why is Turing’s discovery/invention of the Universal Turing Machine so profound?
    It means that truly general-purpose, programmable computing machines exist (i.e., we don’t need specialized machines for all computations).
12. How can we prove there are functions that cannot be computed?
    By diagonalizing over an assumed enumeration of all functions.
13. What does the Church-Turing Thesis say?
    That the Turing Machine lines up exactly with our notion of what is intuitively computable.
14. Why do we think the Church-Turing Thesis is true?
    Because multiple independent formalizations of computation (Turing Machines, Lambda Calculus, μ-recursive functions) all coincide in what they can compute, and no other model has been found that computes more.
15. What does “Turing Complete” mean?
    A computational model that can simulate a Turing Machine.
16. What are the language classes P and NP?
    P is the set of languages decidable in polynomial time on a deterministic TM; NP is the set of languages decidable in polynomial time on a nondeterministic TM.
17. Does P = NP?
18. Did Scott Aaronson really write “everyone who could appreciate a symphony would be Mozart”? How does he feel about writing that these days?
    He did indeed write that but he regrets writing it now.
19. What are some variations we can make to Turing Machines that possibly affect complexity (if not computability)?
    Randomized machines, probabilistic machines, quantum machines.
20. How does Grady Booch distinguish the work in material domains (physics, chemistry, biology, etc.) from that of computer science?
    Scientists in material domains observe the cosmos and reduce it to simple principles; computer scientists start with simple principles and from them create new worlds bound only by the imagination.

Summary