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 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 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.
A Turing machine has four parts:
Computability theory is to examine what kind of problems can a turing machine solve.
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.
This theory examines the time and memory need for a turing machine to solve a problem.
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,