Theory of computation

In theoretical computer science and mathematics, the theory of computation helps us learn about problems that can be solved using a step-by-step plan called an algorithm. It also looks at how fast these problems can be solved and if we can find exact answers or just close guesses, called approximate solutions.

This area has three main parts: automata theory and formal languages, computability theory, and computational complexity theory. These parts all try to answer a big question: "What can and cannot computers do?"

To study how computers work in a careful way, scientists use a simple idea of a computer called a model of computation. One common model they study is the Turing machine. This model is easy to understand and helps scientists learn important facts. The Turing machine is powerful because any problem it can solve can also be solved by a real computer with enough memory. This idea is known as the Church–Turing thesis.

History

The theory of computation started as a way to make models in computer science, using ideas from mathematics and logic. In the last century, it became its own area of study. Special conferences like FOCS began in 1960, and STOC started in 1969. The field also has awards, such as the IMU Abacus Medal, the Gödel Prize, and the Knuth Prize.

Important thinkers who helped shape this field include Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann, and Claude Shannon.

Branches

Automata theory

Main article: Automata theory

Automata theory studies simple machines and the problems they can solve. These machines are called automata, a word from Greek that means "doing something by itself." Automata help us understand what kinds of problems computers can handle. They are also linked to formal language theory, which looks at how languages can be described using sets of symbols.

Formal language theory

Main article: Formal language

Formal language theory is a part of mathematics that describes languages using sets of symbols, called an alphabet. It is closely connected to automata theory because automata can create and recognize these formal languages. There are different levels of complexity in formal languages, each matching a type of automaton that can understand them.

Computability theory

Main article: Computability theory

Computability theory looks at which problems can be solved by computers. One big result is that some problems, like the halting problem, cannot be solved by certain types of computers. This theory also includes Rice's theorem, which tells us that some questions about computer programs cannot be answered by any computer.

Computational complexity theory

Main article: Computational complexity theory

Computational complexity theory asks not only if a problem can be solved by a computer, but also how quickly it can be solved. It looks at two main things: how many steps a computer needs and how much memory it uses. Scientists use special ways to describe these steps, like big O notation, to compare how different problems grow in size. One of the biggest questions in this field is whether certain hard problems can be solved quickly, known as the P versus NP problem.

Grammar	Languages	Automaton	Production rules (constraints)
Type-0	Recursively enumerable	Turing machine	α → β {\displaystyle \alpha \rightarrow \beta } (no restrictions)
Type-1	Context-sensitive	Linear-bounded non-deterministic Turing machine	α A β → α γ β {\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }
Type-2	Context-free	Non-deterministic pushdown automaton	A → γ {\displaystyle A\rightarrow \gamma }
Type-3	Regular	Finite-state automaton	A → a {\displaystyle A\rightarrow a} and A → a B {\displaystyle A\rightarrow aB}

Models of computation

Main article: Model of computation

Computers can be studied in many ways. One common way is called a Turing machine. There are other models too. For example, lambda calculus uses special rules to change and build expressions. Combinatory logic is like lambda calculus but works a little differently. Another model is μ-recursive functions, where calculations are built step by step. The Markov algorithm changes strings of symbols using set rules. Register machines are simple models that use numbers to do tasks. These models help scientists learn what computers can and cannot do.