## What is an algorithm? It's hard to talk about something as vague and ill-defined as "the set of all algorithms,\" so it helps to make things concrete. There's a bunch of ways you might have heard of to formalize the concept of "algorithm.\" There is Turing's idea that represents an algorithm with a Turing machine, there is Church's idea of recursive functions, there are various other formalizations that use various automata. We won't need these. All we need is the idea that any standard programming language (say, Python) is Turing-complete. Pick your favorite Turing-complete programming language; I'll use Python. Because Python is Turing complete, anything a Turing machine does can be expressed in Python, which means that every algorithm can be written in Python (assuming infinite resources, etc.). Formally, we can say that the set of all algorithms can be identified with the set of all semantically-correct Python programs, possibly under some equivalence relation (two programs could express the same algorithm). We want to show this set is countable ## The Kleene Star operator Let $\Sigma$ be some alphabet of characters. The **Kleene star** of this set, denoted $\Sigma^{\star}$, is the set of all *finite* strings built from $\Sigma$. For example, $\left\{0, 1\right\}^\star$ is the set of all *finite* binary strings. Note that the infinite binary string $10101010\ldots$ is *not* part of $\left\{0, 1\right\}^\star$. In short, $\Sigma^\star$ is the set of all finite sequences formed using $\Sigma$, or the set of all sentences that can be written using letters from $\Sigma$. A Python program is just a text file stored on your computer, so if we let $\Sigma$ be the set of all characters on a computer, then every possible Python program belongs to $\Sigma^\star$. In truth, everything stored on a computer is representable through 1s and 0s, so we can also say that every Python program is inside $\{0, 1\}^\star$[^1] **The Kleene star of a finite set is countable.** First enumerate all the sentences with just one letter (so just $\Sigma$), then enumerate all the sentences with two letters, then three, then four, and so on. This gives a way of putting everything in $\Sigma^\star$ in a sequence, forming a bijection between $\Sigma^\star$ and the naturals. Thus, for a finite set $\Sigma$, $\Sigma^\star$ is countable[^2] Since a subset of a countable set is countable, the set of all algorithms is also countable. [^1]: this hints at the deeper truth that we can form a bijection between $\Sigma^\star$ and $\Pi^\star$ for any finite $\Sigma$ and $\Pi$. How? If $\Pi$ is bigger than $\Sigma$ then we can write letters in $\Pi$ using multiple letters from $\Sigma$, and then just do a translation. This is exactly how ASCII works. Moreover, since $\Sigma^\star$ and $\Pi^\star$ are both abstractly in bijection with $\mathbb N$ (as we show), they must also be in bijection with each other. [^2]: A stronger condition is true: for *countable* $\Sigma$, we still have that $\Sigma^\star$ is countable. Why? Well, we know that $\mathbb N \times \mathbb N$ is countable. If $\Sigma$ is in bijection with $\mathbb N$, then we can number the letters $1, 2, 3, \ldots$ and form a bijection between $\Sigma^\star$ and $\mathbb N \times \mathbb N$ by bijecting $(k, \mathbb N)$ with the set of all sentences formed by the *first $k$ letters* in $\Sigma$.