theory of computation not to be confused with computational theory of mind for the journal see theory of computing an artistic representation of a turing machine turing machines are frequently used as theoretical models for computing 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 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 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 finite amount of memory history the theory of computation can be considered the creation of models of all kinds in the field of computer science therefore mathematics and logic are used in the last century it became an independent academic discipline and was separated from mathematics some pioneers of the theory of computation were alonzo church kurt gdel alan turing stephen kleene rzsa pter john von neumann and claude shannon branches automata theory automata theory grammar languages automaton production rules constraints type0 recursively enumerable turing machine displaystyle alpha rightarrow beta no restrictions type1 contextsensitive linearbounded nondeterministic turing machine a displaystyle alpha abeta rightarrow alpha gamma beta type2 contextfree nondeterministic pushdown automaton a displaystyle arightarrow gamma type3 regular finite state automaton a a displaystyle arightarrow a and a a b displaystyle arightarrow ab automata theory is the study of abstract machines or more appropriately abstract mathematical machines or systems and the computational problems that can be solved using these machines these abstract machines are called automata automata comes from the greek word which means that something is doing something by itself automata theory is also closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize an automaton can be a finite representation of a formal language that may be an infinite set automata are used as theoretical models for computing machines and are used for proofs about computability formal language theory formal language set inclusions described by the chomsky hierarchy language theory is a branch of mathematics concerned with describing languages as a set of operations over an alphabet it is closely linked with automata theory as automata are used to generate and recognize formal languages there are several classes of formal languages each allowing more complex language specification than the one before it ie chomsky hierarchy and each corresponding to a class of automata which recognizes it because automata are used as models for computation formal languages are the preferred mode of specification for any problem that must be computed computability theory computability theory computability theory deals primarily with the question of the extent to which a problem is solvable on a computer the statement that the halting problem cannot be solved by a turing machine is one of the most important results in computability theory as it is an example of a concrete problem that is both easy to formulate and impossible to solve using a turing machine much of computability theory builds on the halting problem result another important step in computability theory was rices theorem which states that for all nontrivial properties of partial functions it is undecidable whether a turing machine computes a partial function with that property computability theory is closely related to the branch of mathematical logic called recursion theory which removes the restriction of studying only models of computation which are reducible to the turing model many mathematicians and computational theorists who study recursion theory will refer to it as computability theory computational complexity theory computational complexity theory a representation of the relation among complexity classes complexity theory considers not only whether a problem can be solved at all on a computer but also how efficiently the problem can be solved two major aspects are considered time complexity and space complexity which are respectively how many steps does it take to perform a computation and how much memory is required to perform that computation in order to analyze how much time and space a given algorithm requires computer scientists express the time or space required to solve the problem as a function of the size of the input problem for example finding a particular number in a long list of numbers becomes harder as the list of numbers grows larger if we say there are n numbers in the list then if the list is not sorted or indexed in any way we may have to look at every number in order to find the number were seeking we thus say that in order to solve this problem the computer needs to perform a number of steps that grows linearly in the size of the problem to simplify this problem computer scientists have adopted big o notation which allows functions to be compared in a way that ensures that particular aspects of a machines construction do not need to be considered but rather only the asymptotic behavior as problems become large so in our previous example we might say that the problem requires o n displaystyle on steps to solve perhaps the most important open problem in all of computer science is the question of whether a certain broad class of problems denoted np can be solved efficiently this is discussed further at complexity classes p and np and p versus np problem is one of the seven millennium prize problems stated by the clay mathematics institute in 2000 the official problem description was given by turing award winner stephen cook models of computation model of computation aside from a turing machine other equivalent see churchturing 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 the preceding term by one application of beta reduction combinatory logic is a concept which has many similarities to displaystyle lambda calculus but also important differences exist eg fixed point combinator y has normal form in combinatory logic but not in displaystyle lambda calculus combinatory logic was developed with great ambitions understanding the nature of paradoxes making foundations of mathematics more economic conceptually eliminating the notion of variables thus clarifying their role in mathematics recursive functions a computation consists of a murecursive function ie its defining sequence any input values and a sequence of recursive functions appearing in the defining sequence with inputs and outputs thus if in the defining sequence of a recursive function f x displaystyle fx the functions g x displaystyle gx and h x y displaystyle hxy appear then terms of the form g57 or h3210 might appear each entry in this sequence needs to be an application of a basic function or follow from the entries above by using composition primitive recursion or recursion for instance if f x h x g x displaystyle fxhxgx then for f53 to appear terms like g56 and h563 must occur above the computation terminates only if the final term gives the value of the recursive function applied to the inputs markov algorithm a string rewriting system that uses grammarlike rules to operate on strings of symbols register machine is a theoretically interesting idealization of a computer there are several variants in most of them each register can hold a natural number of unlimited size and the instructions are simple and few in number eg only decrementation combined with conditional jump and incrementation exist and halting the lack of the infinite or dynamically growing external store seen at turing machines can be understood by replacing its role with gdel numbering techniques the fact that each register holds a natural number allows the possibility of representing a complicated thing eg a sequence or a matrix etc by an appropriate huge natural number unambiguity of both representation and interpretation can be established by number theoretical foundations of these techniques in addition to the general computational models some simpler computational models are useful for special restricted applications regular expressions for example specify string patterns in many contexts from office productivity software to programming languages another formalism mathematically equivalent to regular expressions finite automata are used in circuit design and in some kinds of problemsolving contextfree grammars specify programming language syntax nondeterministic pushdown automata are another formalism equivalent to contextfree grammars primitive recursive functions are a defined subclass of the recursive functions different models of computation have the ability to do different tasks one way to measure the power of a computational model is to study the class of formal languages that the model can generate in such a way to the chomsky hierarchy of languages is obtained textbooks aimed at computer scientists there are many textbooks in this area this list is by necessity incomplete hopcroft john e and jeffrey d ullman 2006 introduction to automata theory languages and computation 3rd ed reading ma addisonwesley isbn9780321455369 one of the standard references in the field linz p an introduction to formal language and automata narosa publishing isbn9788173197819 michael sipser 2013 introduction to the theory of computation 3rd ed cengage learning isbn9781133187790 eitan gurari 1989 an introduction to the theory of computation computer science press isbn0716781824 archived from the original on 20070107 hein james l 1996 theory of computation sudbury ma jones bartlett isbn9780867204971 a gentle introduction to the field appropriate for secondyear undergraduate computer science students taylor r gregory 1998 models of computation and formal languages new york oxford university press isbn9780195109832 an unusually readable textbook appropriate for upperlevel undergraduates or beginning graduate students lewis f d 2007 essentials of theoretical computer science a textbook covering the topics of formal languages automata and grammars the emphasis appears to be on presenting an overview of the results and their applications rather than providing proofs of the results martin davis ron sigal elaine j weyuker computability complexity and languages fundamentals of theoretical computer science 2nd ed academic press 1994 isbn0122063821 covers a wider range of topics than most other introductory books including program semantics and quantification theory aimed at graduate students books on computability theory from the wider mathematical perspective hartley rogers jr 1987 theory of recursive functions and effective computability mit press isbn0262680521 s barry cooper 2004 computability theory chapman and hallcrc isbn1584882379 carl h smith a recursive introduction to the theory of computation springer 1994 isbn0387943323 a shorter textbook suitable for graduate students in computer science historical perspective richard l epstein and walter a carnielli 2000 computability computable functions logic and the foundations of mathematics with computability a timeline 2nd ed wadsworththomson learning isbn0534546447 theory of computation at mit theory of computation at harvard computability logic a theory of interactive computation the main web source on this subject vteareas of mathematics outline topic lists branchesalgebra linear multilinear abstract elementary arithmetic number theory calculus analysis differential equations dynamical systems numerical analysis optimization functional analysis geometry discrete algebraic analytic differential finite topology trigonometry foundations philosophy of mathematics mathematical logic set theory category theory applied mathematical physics probability mathematical statistics statistics game theory information theory computer science computation control theory others history of mathematics recreational mathematics mathematics and art mathematics education order theory graph theory divisions pure applied discrete computational category portal commons wikiproject 