Theory of Computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory and computational complexity theory.

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). 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.

Read more about Theory Of Computation:  History, Models of Computation

Other articles related to "theory of computation, theory, of computation, computation, of computations":

Computer Science Education - Areas of Computer Science - Theoretical Computer Science - Theory of Computation
... be (efficiently) automated?" The study of the theory of computation is focused on answering fundamental questions about what can be computed and what ... In an effort to answer the first question, computability theory examines which computational problems are solvable on various theoretical models of computation ... second question is addressed by computational complexity theory, which studies the time and space costs associated with different approaches to solving a multitude of ...
Theory Of Computation - Models of Computation
... from a Turing machine, other equivalent (See Church–Turing thesis) models of computation are in use ... Lambda calculus A computation consists of an initial lambda expression (or two if you want to separate the function and its input) plus a finite sequence of lambda terms, each deduced from ... mu-recursive functions a computation consists of a mu-recursive function, i.e ...
Outline Of Computer Science - Subfields - Theory of Computation
... Automata theory – Different logical structures for solving problems ... Computability theory – What is calculable with the current models of computers ... in computer science Computational complexity theory – Fundamental bounds (especially time and storage space) on classes of computations ...

Famous quotes containing the words computation and/or theory:

    I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...
    Minnie Maddern Fiske (1865–1932)

    every subjective phenomenon is essentially connected with a single point of view, and it seems inevitable that an objective, physical theory will abandon that point of view.
    Thomas Nagel (b. 1938)