Fields
Theory of Computation
Also Known As Computability Theory
Field of Study
Citation Formats
General Reference
APA Style
BibTeX
Theory of computation is a branch of theoretical computer science and mathematics investigating which problems can be solved by computational models and algorithms, and how efficiently. It comprises three interconnected areas: automata theory, computability theory and computational complexity theory.
Facts
Origin Year1960 marks the founding of FOCS, one of the field's formative conferences, not a single invention date; the discipline developed gradually over the mid twentieth century. Core ConcernDetermining which problems are computable at all, at what efficiency, and to what accuracy, building on the foundational work of Alan Turing, Alonzo Church, Kurt Godel, Stephen Kleene, John von Neumann and Claude Shannon. 1 Cross-Tradition Connections
Sources
1. Wikipedia: Theory of Computation
Wikimedia FoundationHistory sectionQuote, History section
The theory of computation can be considered the creation of models of all kinds in the field of computer science.
1. Wikipedia: Theory of Computation
Wikimedia FoundationHistory section, founding figuresQuote, History section, founding figures
Some pioneers of the theory of computation were Ramon Llull, Alonzo Church, Kurt Godel, Alan Turing, Stephen Kleene, Rozsa Peter, John von Neumann and Claude Shannon.
1. Wikipedia: Theory of Computation
Wikimedia FoundationHistory section, FOCS foundingQuote, History section, FOCS founding
In the last century, it separated from mathematics and became an independent academic discipline with its own conferences such as FOCS in 1960 and STOC in 1969.
1. Wikipedia: Theory of Computation
Wikimedia FoundationIntroductionQuote, Introduction
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation using an algorithm, how efficiently they can be solved and to what degree.
Wikipedia: Finite-state machine
Wikimedia FoundationIncludes: Finite State Machine, General descriptionView the Source Wikipedia: Regular expression
Wikimedia FoundationIncludes: Regular Expression, History sectionView the Source Wikipedia: Quantum computing
Wikimedia FoundationAssociated With: Quantum Computing, Algorithms sectionQuote, Associated With: Quantum Computing, Algorithms section
Quantum algorithms can be roughly categorized by the type of speedup achieved over corresponding classical algorithms.
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.