Difference between revisions of "Theory of computation"

Latest revision as of 15:52, 20 April 2016

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

Branches

The field is divided into three major branches:

• Automata theory and language
• Computability theory
• Computational complexity theory

These branches are linked by the question: "What are the fundamental capabilities and limitations of computers?."

Turing machine

In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation.

There are several models in use, but the most commonly examined is the Turing machine.

Computer scientists study the Turing machine because:

• It is simple to formulate
• It can be analyzed and used to prove results
• It represents what many consider the most powerful possible "reasonable" model of computation (see Church–Turing thesis)

It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem solved by a Turing machine will always require only a finite amount of memory. So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a bounded amount of memory.

See also

• Algorithm
• Computability
• Computation
• Computation theory
• Model of computation
• Turing machine
• Universal Turing machine

External links

• Theory of computation @ Wikipedia