Theory of computation

Topic | v1 | created by jjones |

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. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?". 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, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation (see Church–Turing thesis).


subtopic of Computer science

Computer science is the study of computation and information. Computer science deals with theory of c...

Edit details Edit relations Attach new author Attach new topic Attach new resource

treated in Introduction to Complexity and Computability

7.5 rating 3.5 level 6.0 clarity 3.5 background – 2 ratings

This is a basic course on the theory of algorithms, computability and computational complexity. Rough...

relates to Complexity ZOO

5.0 rating 8.0 level 5.0 clarity 2.0 background – 1 rating

The sprawling web of known relations among complexity classes - containments, oracle separations, ran...

treated in Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak

This is a textbook on computational complexity theory. It is intended as a text for an advanced under...

treated in Introduction to the Theory of Computation, 3rd edition

Gain a clear understanding of even the most complex, highly theoretical computational theory topics i...