This course explores the fundamental question: what can be computed, and what can be described? We begin with formal languages — infinite sets of strings captured by finite descriptions — and the automata and grammars that recognise or generate them. Through rewrite systems, we see how simple substitution rules can encode complex behaviour. Regular languages introduce the first automata model (finite state machines) and show that some languages fall outside their reach. Context-free languages extend our expressiveness through grammars, capturing phenomena like nested parentheses that regularity cannot handle. Yet even these have limits. Register machines provide a model of computation closer to real computers, manipulating words in unbounded memory. Finally, computability theory crowns the journey: we prove that some problems — like the halting problem — are fundamentally undecidable, no matter how powerful our machines.

The course is organised around the Chomsky hierarchy, a pyramid of language classes of increasing power. Each level asks: what can be computed or recognised at this tier? Yet power comes with a cost. We discover a critical gap between describing a language (giving a grammar or recognising device) and deciding it (answering "is this word in the language?" algorithmically). Regular languages sit squarely in the decidable zone. Context-free languages mostly do too, though some decision problems become hard. But as we climb toward register machines and general computation, we hit the ceiling: some properties — like whether a machine halts — are provably undecidable. This tension between finite description and infinite behaviour, between what we can express and what we can decide, is the heartbeat of the course.

Each chapter builds naturally on the last. Rewrite systems give us a grammar-like tool to reason about transformations. Regular languages and finite automata establish our baseline — expressive enough for lexical scanning, but too weak for parsing. Context-free languages let us handle recursion and nesting, the grammar of programming languages themselves. Register machines bridge to general computation, making the step to computability tangible. Computability theory then reveals the fundamental limits: through Rice's theorem, we see that almost all non-trivial questions about what programs compute are undecidable. By the end, the reader sees why some problems are hard in practice (complexity), while others are impossible in principle (uncomputability).

# 1. Introduction

This chapter establishes the conceptual and notational foundations of the course. The central question sounds simple but has no naive answer: what does it mean for something to be *computable*? The answer turns out to require a precise mathematical framework — one built from strings over finite alphabets — and the combinatorial properties of these string sets illuminate both the scope and the limits of computation. This chapter motivates the need for formal definitions, introduces the basic objects of the theory, and records the set-theoretic infrastructure that the rest of the course depends on.

## Why Formal Definitions of Computation?

There is a fundamental asymmetry between positive and negative results in mathematics. A positive result — showing that some algorithm exists — does not require a formal definition of "algorithm", because we can agree on a concrete procedure when we see one. A negative result — showing that *no* algorithm can solve a given problem — requires ruling out every conceivable algorithm, and that demands a rigorous definition.

[motivation] ### The Gap Between Existence and Computability Consider two statements about polynomials $p \in \mathbb{Z}[X]$ of degree $n$: 1. Every polynomial of degree $n$ has a root (in $\mathbb{C}$). 2. There is an algorithm that, given a polynomial of degree $n$, finds a root. The first statement is the Fundamental Theorem of Algebra, and its proof is purely existential. The second statement is a claim about algorithmic access, and it demands specifying what an algorithm actually is. In many areas of mathematics, existence proofs are known while constructive algorithms are not — and sometimes provably cannot — exist. ### Hilbert's Programme and the Entscheidungsproblem In 1900, David Hilbert presented his celebrated list of mathematical problems at the International Congress in Paris. The tenth problem asked for an algorithm to decide whether a Diophantine equation — a polynomial equation $p(x_1, \ldots, x_n) = 0$ with coefficients in $\mathbb{Z}$ — has integer solutions. Hilbert expected the answer to be yes. The problem was eventually resolved negatively by Matiyasevich in 1970, building on work of Davis, Putnam, and Robinson: no such algorithm exists. The Entscheidungsproblem (decision problem) was formulated in 1928 by Ackermann in the book *Grundzüge der theoretischen Logik*: given a first-order logical formula $\varphi$, determine whether $\varphi$ is a tautology — that is, whether it is true under every interpretation of its variables. Again, Hilbert expected a positive solution. Church and Turing independently showed in 1936 that no such algorithm exists. Their proofs required, for the first time, a rigorous mathematical definition of "algorithm". [/motivation]

The lesson of these examples is clear: to prove a problem is algorithmically unsolvable, one must first pin down exactly what counts as an algorithm. The rest of this course is devoted to making that definition precise, and to understanding the landscape of what is and is not computable.

## Alphabets and String Spaces

Computation operates on data. Before defining what a computation *does*, we must define what it operates *on*. Modern computation encodes all objects — numbers, polynomials, logical formulas, programs — as finite strings over a finite set of symbols, just as digital computers encode everything in bits.

[definition: Alphabet and String Space] An **alphabet** (or set of symbols) is a set $\Omega$, which we typically assume to be finite. The **set of $\Omega$-strings** $\Omega^\star$ is the set of all finite sequences of elements of $\Omega$, including the empty sequence $\varepsilon$. More precisely, using the von Neumann identification of $n = \{0, 1, \ldots, n-1\}$, we define $\Omega^n := (n \to \Omega)$ as the set of functions from $n$ to $\Omega$ — equivalently, sequences of length $n$. Then: \begin{align*} \Omega^\star = \bigcup_{n \in \mathbb{N}} \Omega^n. \end{align*} The **length** of a string $\alpha \in \Omega^\star$ is written $|\alpha| = \operatorname{domain}(\alpha)$. [/definition]

The choice to work with strings rather than numbers is not a loss of generality. Any finite mathematical object can be encoded as a string: the encoding is part of the model. Binary strings (where $\Omega = \{0,1\}$) suffice for everything, but working with a general alphabet $\Omega$ keeps the formalism cleaner in many settings.

[example: Concrete Alphabets] Take $\Omega = \{0, 1\}$. Then $\Omega^3$ consists of the eight bit-strings $000, 001, 010, 011, 100, 101, 110, 111$. The empty string $\varepsilon \in \Omega^0$ is the unique element of $\Omega^0 = (0 \to \Omega)$. Take $\Omega = \{a, b, \ldots, z\}$, the lower-case English letters. Then $\Omega^\star$ contains the empty string, all single letters, all pairs $aa, ab, \ldots, zy, zz$, and so on. The string "hello" is an element of $\Omega^5$. Now consider the **boundary**: what happens when $\Omega = \varnothing$? The definition gives $\Omega^0 = (0 \to \varnothing)$, which contains exactly one element — the empty function $\varepsilon$. But $\Omega^1 = (1 \to \varnothing) = \varnothing$, since there is no function from a one-element set to the empty set. So $\Omega^\star = \{\varepsilon\}$ when $\Omega = \varnothing$: the empty alphabet admits only the empty string. This is not merely an edge case — it is why the Countability Theorem for $X^\star$ requires $X \neq \varnothing$ (the empty alphabet produces a finite, not infinite, string space). Any algorithm that processes strings over a nonempty alphabet can be contrasted with this degenerate case to test whether a result really depends on having at least one symbol available. [/example]

## Notational Conventions for Strings

The course uses a carefully set up notation for manipulating strings. These conventions are worth recording explicitly, as they recur throughout.

[definition: String Operations] Fix an alphabet $\Omega$. The following operations and conventions apply: - **Natural numbers**: $\mathbb{N} := \{1, 2, 3, \ldots\}$. For indexing string positions and lengths, we use the von Neumann ordinal construction extended to include $0$: write $\mathbb{N}_0 := \{0, 1, 2, \ldots\} = \mathbb{N} \cup \{0\}$, and identify each $n \in \mathbb{N}_0$ with the set $\{0, 1, \ldots, n-1\}$ of all smaller non-negative integers. The string space is then $\Omega^\star = \bigcup_{n \in \mathbb{N}_0} \Omega^n$. - **String length**: For $\alpha \in \Omega^n$, we write $|\alpha| = n$. - **Empty string**: $\Omega^0 = (0 \to \Omega)$ has exactly one element, $\varepsilon$, the empty sequence. - **Truncation**: For $\alpha \in \Omega^n$ and $k \leq n$, the truncation $\alpha|_k \in \Omega^k$ is the unique sequence of length $k$ such that $\alpha|_k \subseteq \alpha$ (viewing sequences as functions, $\alpha|_k$ is the restriction of $\alpha$ to $\{0, \ldots, k-1\}$). - **Concatenation**: For $\alpha \in \Omega^m$ and $\beta \in \Omega^n$, their concatenation $\alpha\beta \in \Omega^{m+n}$ is defined piecewise: \begin{align*} (\alpha\beta)(i) = \begin{cases} \alpha(i) & i < m \\ \beta(i - m) & m \leq i < m + n. \end{cases} \end{align*} - **Powers of strings**: By recursion, $\alpha^0 := \varepsilon$ and $\alpha^{n+1} := \alpha \cdot \alpha^n$. - **Singletons**: An element $x \in \Omega$ is identified with the string $(x) \in \Omega^1$. - **Language concatenation**: For sets $Y, Z \subseteq \Omega^\star$, write $YZ := \{\alpha\beta \mid \alpha \in Y,\, \beta \in Z\}$. For a singleton $Y = \{\alpha\}$, write $\alpha Z := \{\alpha\beta \mid \beta \in Z\}$. - **Functorial lift**: A function $f: \Omega \to \Lambda$ lifts to a function $\hat{f}: \Omega^\star \to \Lambda^\star$ by applying $f$ componentwise. The hat is often omitted when context is clear. [/definition]

The definitions above are more elaborate than they might initially appear — the identification of natural numbers with sets, the uniform treatment of $\Omega^0$, and the explicit piecewise formula for concatenation all serve a purpose. When we come to define Turing machines and register machines, these conventions allow us to encode programs as strings and to reason about string operations algebraically rather than informally. The notation pays for itself.

[remark: Why Von Neumann Ordinals?] The identification $n = \{0, 1, \ldots, n-1\}$ lets us write $\Omega^n = (n \to \Omega)$ uniformly, treating the length as a set (the domain of the function). This unifies the definitions of $\Omega^0$, $\Omega^n$, and $\Omega^\star$ without introducing separate notation for each case, and makes truncation ($\alpha|_k = \alpha\upharpoonright k$) a standard restriction of functions. [/remark]

## Countability of String Spaces