Theory of computation

Theory of computation is a branch of theoretical computer science and mathematical science. It mainly includes three branches, which are automata theory, computability theory, and computational complexity theory respectively.

Automata theory

Automata theory is closely linked to formal language theory. Formal language is a set of strings of symbols that may be constrained by rules that are specific to it. Formal language is created for the mathematical sake, because doing so makes mathematician be able to express computation and proof clearly and logically. Automata is an abstract model of machine that can potentially generate all the element in a formal language. For a inaccurate instance, if a formal language is all positive integers that are even, a automata could be n=2 ; n=n+2 . We see that the formal language is an infinite set, but its automata machine is a finite representation.

Turing Machine

Turing machine may be one of the most famous automata.

A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

From the definition in Wikipedia, what we can get is that: first, turing machine is only a hypothetical machine, it is not real, but only a model. It is widely accepted, because it is extremely useful when using to explaining how our computer works, so that it can help computer scientists understand the limits of mechanical computation. However, this is not its initial purpose. Like all other automata, Turing machine was invented to study problems in math.

Brief description of Turing machine's structure

A Turing machine has four parts:

  1. Tape : the tape is usually infinite long, and divided into cells. Each cell contain an alphabet or a blank.
  2. Head : A head can read or write at a cell, or move one step to either left or right at a time.
  3. State Register : it stores the state of Turing machine, one of the finite many.
  4. Action Table : It is actually a function from the state of machine and read of head to instructions to machine. Note that if there is only one set of action table, then the Turing machine is a determined Turing machine, if there is a tree of action tables then it is a Non-determined Turing machine.

Computability theory

Computability theory is to examine what kind of problems can a turing machine solve.

Church–Turing thesis

The Church–Turing thesis states that if some method (algorithm) exists to carry out a calculation, then the same calculation can also be carried out by a Turing machine.

Computational complexity theory

This theory examines the time and memory need for a turing machine to solve a problem.

P and NP prblem

This problem is a huge problem in the field of computational complexity theory. It asks that if determined turing machine and Non-determined turing machine are time-costly equivalent which means if a problem can be solved by NDTP in a polynomial time, can it be solved in DTP in a polynomial time too? Simply put, it asks whether the complexity of algorithms of examination is the same level as the algorithms of search. For example,


  1. Formal Language
  2. Automata Theory
  3. Turing Machine


  1. They keeps saying that computational theory is hugely used in AI field, how is that?
  2. Why can't we create computers that are equivalent to turing machine?