Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 59 ยท Getting Started

What Is the Theory of Computation?

Learn what the theory of computation studies: abstract machines, languages, decision problems and the limits of what computers can solve, with Python examples.

Every program you have ever written runs on a real computer with a particular processor, memory size and operating system. The theory of computation steps back from all of that and asks questions that hold for every computer, past, present and future. What does it even mean to "compute" something? Which problems can a machine solve? Which problems can a machine never solve, no matter how clever the programmer or how fast the hardware? And among the solvable ones, which can be solved quickly?

These questions sound abstract, but the answers shape practical tools you use daily: the regular expression engine in your editor, the parser inside every compiler, the validators in your web forms, and the reason a "perfect bug finder" can never exist. This course builds the ideas one layer at a time, with small Python programs you can run in the page.

The three big questions

The theory is usually split into three branches, each asking a different question about problems.

  1. Automata theory asks: what are the simplest machines, and what can each kind recognize? You will meet finite automata, pushdown automata and Turing machines.
  2. Computability theory asks: is there any algorithm at all for this problem? Some problems have none, and we can prove it.
  3. Complexity theory asks: if an algorithm exists, how many resources (time, memory) does it need? This is where the famous P versus NP question lives.

Three questions

Automata What can each machine recognize?
Computability Is there any algorithm?
Complexity How much time and memory?

This course covers all three, in this order.

1 / 3

Problems become "does this string belong?"

To reason about all problems with one simple tool, the theory converts them into decision problems: questions with a yes or no answer. "Is this number prime?" is a decision problem. "Find the shortest route" is not, but it can be rephrased: "Is there a route shorter than 50 km?"

Then every decision problem is encoded as a question about a string. Write the input as text, and ask whether that text belongs to a set of "good" strings. A set of strings is called a language. A machine recognizes a language if it says yes to exactly the strings in it. So "solving a problem" and "recognizing a language" are two names for the same thing, and that is the whole reason formal languages sit at the center of this subject (you will define them carefully in Alphabets, Strings and Languages).

Python A decision problem is a yes/no function on strings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each function above is a tiny machine for a language: the set of even-length strings, and the set of binary palindromes. Notice how different they feel. The first needs almost no memory (just a toggle between "even so far" and "odd so far"). The second must remember the whole first half of the input to compare it with the second half. That difference in memory needs is exactly what the hierarchy of machines measures.

Models of computation

A model of computation is a precise, minimal description of what a machine is allowed to do. Models are deliberately stripped down so we can prove things about them.

  • A finite automaton reads the input once from left to right and has a fixed, finite number of states. It cannot count without limit.
  • A pushdown automaton adds a stack, so it can match nested structure like parentheses.
  • A Turing machine has an unbounded tape it can read and write in both directions. It is believed to capture everything that any computer can compute (the Church-Turing thesis, covered later).

Let us see the memory difference in running code. The first program below has a fixed number of states. The second needs a counter that can grow as large as the input.

Python Finite memory versus unbounded memory

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

even_as would work unchanged on a string a billion characters long, because its memory is one of two labels. an_bn needs count to hold numbers up to half the input length. In Finite Automata you will prove that no machine with a fixed number of states can recognize a^n b^n.

Why a hierarchy?

The big structural result of the field is that these models form a ladder. Every language a finite automaton can recognize is also recognizable by a pushdown automaton, and every pushdown language is recognizable by a Turing machine, but not the other way around. Noam Chomsky described a matching ladder for grammars, which you will study in Grammars and the Chomsky Hierarchy.

flowchart TB
    R["Regular languages<br/>finite automata"] --> C["Context-free languages<br/>pushdown automata"]
    C --> S["Context-sensitive languages<br/>linear bounded automata"]
    S --> E["Recursively enumerable languages<br/>Turing machines"]

Each class contains the one above it in the picture. Moving down gains power and loses guarantees.

What you will be able to do

By the end of the course you will be able to design a DFA or NFA for a described language, convert between automata and regular expressions, write grammars and parse trees, build pushdown automata, trace a Turing machine, prove that some languages are not regular or not context-free, explain why the halting problem is undecidable, and recognize NP-complete problems. Every chapter has code, because the best way to understand a machine is to build one.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which branch of the theory asks whether any algorithm exists for a problem?

    Computability theory studies what can be solved by any algorithm at all, independent of speed or memory. Complexity theory then asks how expensive solvable problems are.
  2. 2. How is a decision problem turned into a language?

    The language of a decision problem is the set of all encoded inputs for which the correct answer is yes. Recognizing the language and solving the problem are the same task.
  3. 3. Which machine model has only a fixed, finite number of states and no other memory?

    A finite automaton remembers only its current state. A pushdown automaton adds a stack and a Turing machine adds a rewritable tape.
  4. 4. Why can a program for a^n b^n not be a finite automaton?

    The count of a's can be arbitrarily large, so no fixed number of states can remember it. A stack or counter is needed.

Summary

  • The theory of computation studies what machines can compute (computability) and how efficiently (complexity), using minimal abstract models.
  • Problems are modeled as decision problems, and decision problems as languages: sets of strings.
  • Machine models form a ladder of increasing power: finite automata, pushdown automata, Turing machines.
  • The key resource that separates the rungs is memory: none beyond states, a stack, or a full tape.
  • Later chapters give each rung a precise definition and prove what it cannot do.

Next: Alphabets, Strings and Languages