What Can Computers Actually Solve, and How Do We Know?

One thing I keep coming back to as I learn more about computer science is how rarely we stop to ask a really basic question: what can a computer actually do?

Not in the hardware sense. Not "how fast can it run" or "how much memory does it need." But in a deeper sense — what kinds of problems are even solvable by a machine? And if we have two problems, how do we decide which one is harder?

These sound like philosophy questions, but they're not. There are precise, formal answers. And the framework for finding those answers is called the theory of computation.

This is the start of a new series where I'll walk through the core ideas — from the simplest machines to the most powerful ones — and try to figure out where the boundaries of computation actually are. The progression follows Sipser's Introduction to the Theory of Computation, which is the standard textbook for this material.

It all starts with a yes-or-no question

The first thing to understand is that this entire field simplifies problems down to one type: decision problems.

A decision problem is any question where the answer is either yes or no. That's it. Binary. True or false. One or zero.

This framing isn't new. In 1928, David Hilbert and Wilhelm Ackermann posed the Entscheidungsproblem — literally "the decision problem" — asking whether some algorithm could read any mathematical statement and answer yes or no, mechanically. The whole field grew out of trying to answer that one question.

That might feel limiting, but here's the key insight: almost any problem can be reframed as a decision problem.

• "What's the shortest path from A to B?" is an optimization problem.
• "Does a path from A to B exist?" is a decision problem.

The optimization version asks what the answer is. The decision version asks whether an answer exists. And it turns out that understanding the yes/no version gives you a huge amount of leverage on the harder question too.

Some decision problems are harder than others

Here's a thought experiment. Consider these four problems:

1. Does a particular file exist on your computer?
2. Will this code compile?
3. Does a runtime error exist in this code?
4. Is your system completely unhackable?

The first one? Just search the file system. The second one? Run the compiler — it either succeeds or throws an error. Those are things tools can handle reasonably well.

But certifying that a system is completely unhackable? You can test against known attacks, but how do you guarantee there isn't some technique you haven't thought of? That feels fundamentally harder — and as we'll see later in this series, it actually is, in a formally provable way. Rice's theorem (1953) is the formal version of "you can't decide non-trivial properties of arbitrary programs."

A 30-minute tour of how Gödel and Turing proved some yes/no questions can never be answered by any machine.

The point is that "hardness" isn't just vibes. There's a rigorous hierarchy, and building up to it is what this series is about.

Before we get to the formal definitions, try ranking your own intuition. Drag these five problems onto the axis from easiest on the left to "I'm not sure any algorithm can do this" on the right, then reveal the formal class behind each one.

Every input is just a string

Here's the model. For any decision problem:

• The input is a string.
• The output is yes or no.

Now, in practice, inputs can be graphs, lists, integers, images — all kinds of things. But every single one of those can be encoded as a string of characters. The trick is old: Gödel numbering showed back in 1931 that you can turn any logical statement into a single number. So the theory assumes the encoding has already happened, and we just work with strings.

That single simplification is what makes the whole framework tractable. No matter how complex the original problem is, we can always reduce the question to: "given this string, yes or no?" Turing leaned on exactly this trick in his 1936 paper, the one that defined what a "computing machine" even means.

The building blocks: alphabets, strings, and languages

To work with strings formally, we need a few definitions.

An alphabet (written as Σ) is a finite, non-empty set of symbols. Think of it like the characters you're allowed to use.

A string (or word) is a sequence of symbols from that alphabet. The length of a string is the number of symbols in it. And there's one special string: the empty string (written ε), which has length zero.

A language is just a set of strings. That's the formal term for "a collection of strings that share some property we care about."

So when we talk about a decision problem, we're really asking: "does this input string belong to this language?"

Absolute value signs mean different things depending on what's inside

One quick detour that catches people. The notation |x| means different things depending on the type of x:

They're all related to "size" in some sense, but the precise meaning depends on the data type. In this field, we'll mostly use it for sets (cardinality) and strings (length).

Building languages with three operations

Now that we have languages, we need ways to combine them. There are three fundamental operations: union, concatenation, and Kleene star.

Union

Union is what you'd expect. If R₁ and R₂ are languages, then R₁ ∪ R₂ is the language containing any string that's in either R₁ or R₂.

Notice that ba appears in both sets, but in the union we only list it once. Sets don't have duplicates — an element is either in the set or it isn't. The cardinality here is 5, not 6.

Concatenation

If R₁ and R₂ are languages, then R₁ ∘ R₂ (R₁ concatenated with R₂) is the language of all strings you can make by taking one string from R₁ and gluing one string from R₂ onto the end.

Here's the thing that makes concatenation different from the Cartesian product: you can get duplicates. If ab ∘ ε = ab and a ∘ b = ab, those produce the same string. But since the result is a set, ab only appears once.

Let me walk through a concrete example. Let R₁ = {ab, ba, a} and R₂ = {bb, b, ε}.

The resulting language is {abbb, abb, ab, babb, bab, ba, a} — seven unique strings, not nine.

This is also why concatenation is not commutative. Swapping R₁ and R₂ gives you a different language because the order of the gluing matters.

Kleene star

Kleene star is an operation on a single language. R* means: take every possible combination of concatenations of strings from R, including zero concatenations.

The key things to remember:

1. ε is always in R.* Always. No matter what R is. Because zero concatenations gives you the empty string.
2. R is usually infinite.* You can keep concatenating more and more strings, creating longer and longer results.

There are only two exceptions — two languages whose Kleene star produces a finite result:

The empty language starred gives you just {ε}. The language containing only the empty string starred also gives you just {ε}. Every other language produces an infinite set under Kleene star.

Here's a quick example. If R = {a, bc, ε}, then R* includes:

• ε (zero concatenations)
• a, bc (single elements)
• aa, abc, bca, bcbc, a, bc (two concatenations — some are duplicates)
• aaa, aabc, abca, ... (three concatenations)
• ... and it keeps going

The result is an infinite language containing all possible combinations of a's and bc's strung together.

If you want to feel how these three operations actually behave, here's a live playground. Type any two finite languages (use ε for the empty string), and see the union, concatenation, and Kleene star recompute as you type. The cap on Kleene star is what stops it from running forever.

The empty set and the empty string are completely different things

This trips people up, so let me be explicit.

∅ is an empty box. ε is a zero-length word. They're completely different data types that happen to both involve "nothing." Don't mix them up.

Regular expressions: a way to describe languages

Everything we've built so far — alphabets, strings, languages, union, concatenation, Kleene star — comes together in regular expressions.

A regular expression is not a language. It's a description of a language. The same way "all even numbers" describes a set, a regular expression describes a set of strings.

The basic symbols

For an alphabet Σ = {0, 1}, the building blocks of regular expressions are:

Each basic symbol describes a language with at most one string in it.

The operations

We combine these basic symbols using the same three operations:

• Union (written as ∪ or sometimes |)
• Concatenation (usually just written by putting things next to each other)
• Kleene star (written as *)

And we use parentheses for grouping.

Order of operations

Just like arithmetic has multiplication before addition, regular expressions have:

1. Kleene star first (highest precedence)
2. Concatenation second
3. Union last (lowest precedence)

So ab* means "a followed by zero or more b's" — the star only applies to b, not to ab.

Notation: L(R)

To be precise about the difference between a regular expression R and the language it describes, we write L(R) — "the language described by R."

This keeps things clean. R is the description. L(R) is the actual set of strings.

A few examples

Let's work through some with alphabet Σ = {a, b}.

Example 1: The language {a, b, c}.

Regular expression: a ∪ b ∪ c

Because a by itself means {a}, and union combines them.

Example 2: The language {aⁿ : n ≥ 0} = {ε, a, aa, aaa, ...}

Regular expression: a*

Kleene star gives us every possible number of a's, including zero.

Example 3: The language {aⁿ : n ≥ 1} = {a, aa, aaa, ...}

Regular expression: a*a (or equivalently aa*)

We take all the a-strings from Kleene star and concatenate one more a, which shifts everything up by one and removes ε.

We can also draw this same language as a finite automaton — read one a to reach the accept state, and stay there for any extra as:

The fact that a regex and a state machine describe the same language is the bridge to the next post in this series.

Example 4: The language {a, ab, abb, abbb, ba, bab, babb, babbb}

This one's trickier. Let me break it down:

Wait — but we can simplify. The b-part at the end is {ε, b, bb, bbb}. That's not quite b* (which would include bbbb, bbbbb, ...). So we have to list them explicitly: (ε ∪ b ∪ bb ∪ bbb).

And the front part {ε, ba} gives us the optional ba prefix.

So the full regular expression is: (ε ∪ ba) a (ε ∪ b ∪ bb ∪ bbb)

But wait — can we simplify further? That back part is actually (ε ∪ b ∪ bb ∪ bbb). If it were infinite, we could write b*. But since it stops at three b's, we can't use Kleene star alone. We'd need to write it out.

Here's the thing I find interesting about regular expressions: the notation itself is limited to just three operations. No subtraction, no intersection. And yet, as we'll see, these three operations are enough to describe a surprisingly large class of languages.

Where this is heading

This series is going to follow a progression through three types of computational models:

1. Finite automata — the simplest machines. They read input one character at a time with no memory beyond their current state. Regular expressions describe exactly the languages these machines can recognize.

2. Pushdown automata — finite automata with a stack. That extra memory lets them handle a broader class of languages (context-free languages), which includes things like matching parentheses and parsing programming language syntax.

3. Turing machines — the most powerful model. They have unlimited memory and can move in both directions along the input. This is where things get really interesting, because we'll discover that even Turing machines have limits. There are problems they provably cannot solve.

The second half of the series will be about pushing Turing machines to their breaking point — finding out exactly where computation ends. The reason we trust that limit is the Church-Turing thesis: Alonzo Church and Alan Turing independently showed that every reasonable definition of "computable" lands on the same class of problems.

📺 Lecture series: MIT 18.404J — Theory of Computation, Sipser (Fall 2020) — free MIT OCW course taught by the author of the textbook this series follows.

A few things I'm taking away

• Every computational problem can be reframed as a decision problem — a yes/no question about whether a string belongs to a language
• Not all decision problems are equally hard, and the theory gives us a formal way to compare difficulty levels — not just intuition
• Alphabets, strings, and languages are the basic vocabulary, and everything builds on these three concepts
• Union, concatenation, and Kleene star are the only three operations needed to build up complex languages from simple ones
• Kleene star always includes the empty string — zero concatenations is a valid option, and that's by definition
• The empty set and the empty string are completely different types of objects that happen to share the concept of "nothing"
• Regular expressions are descriptions of languages, not languages themselves — the notation L(R) keeps that distinction clear
• Concatenation of languages can produce duplicates that collapse in the result, making it different from the Cartesian product
• Regular expressions use just three operations and parentheses — no subtraction, no intersection — yet they can describe a surprisingly rich class of languages
• The simplest machines (finite automata) and regular expressions turn out to describe the same class of languages — that equivalence is one of the most beautiful results in this field

That last one is what the next post will dig into. The idea that two completely different formalisms — one mechanical (a machine reading characters), one algebraic (a pattern built from operations) — end up capturing exactly the same set of languages is the kind of result that makes this field feel less like abstract math and more like discovering something fundamental about computation itself.