Theory of computation

In theoretical computer science and mathematics, the theory of computation is a special area that helps us understand what problems can be solved using a step-by-step plan called an algorithm. It also looks at how quickly these problems can be solved and whether we can find exact answers or just close guesses, known as approximate solutions.

This field is split into three main parts: automata theory and formal languages, computability theory, and computational complexity theory. All of these parts try to answer a big question: "What are the fundamental capabilities and limitations of computers?"

To study computation in a careful and exact way, computer scientists use a simple idea of a computer called a model of computation. One of the most common models they study is the Turing machine. This model is easy to describe and analyze, and it helps scientists discover important facts. The Turing machine is powerful because, even though it seems to need unlimited memory, any problem it can solve only needs a limited amount of memory to do so. This means that any problem a Turing machine can solve can also be solved by a real computer with enough memory. This powerful idea is known as the Church–Turing thesis.

History

The theory of computation began as a way to create models in computer science, using ideas from mathematics and logic. In the last century, it became its own area of study with special conferences like FOCS starting in 1960 and STOC in 1969. It also has its own 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, called automata, come from a Greek word meaning "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 not only asks 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 thought of in many different ways when we study how they work. One common way is called a Turing machine, but there are other similar models too. For example, there is something called lambda calculus, which uses special rules to change and build expressions. There is also combinatory logic, which is like lambda calculus but has some differences. Another model is called μ-recursive functions, where calculations are built step by step using simple rules. The Markov algorithm changes strings of symbols using set rules, and register machines are simple models that use numbers to perform tasks. These different models help scientists understand what computers can and cannot do.