Complexity Theory Codexery

Theory of computation

Study of computability, complexity, and models of computation.

Last updated

The theory of computation examines which problems can be solved algorithmically, how efficiently they can be solved, and to what degree solutions can be approximated.[1] Its three central branches are automata theory, computability theory, and computational complexity theory.[1]

Quick Facts

Field
Theoretical computer science and mathematics
Branches
  • Automata theory and formal languages
  • computability theory
  • computational complexity theory
Key concept
Model of computation (e.g., Turing machine)
Major open problem
P versus NP problem (one of the seven Millennium Prize Problems)
Pioneers
  • Ramon Llull
  • Alonzo Church
  • Kurt Gödel
  • Alan Turing
  • Stephen Kleene
  • Rózsa Péter
  • John von Neumann
  • Claude Shannon

Facts from the source article.

Key facts and history

The field uses mathematical abstractions called models of computation, such as the Turing machine, to study computation rigorously.[2] Formal language theory, closely linked to automata theory, describes languages as operations over an alphabet and is organized by the Chomsky hierarchy.[3] A landmark result is that the halting problem cannot be solved by a Turing machine.[4] Rice's theorem further states that any non-trivial property of partial functions is undecidable for Turing machines.[5]

Computability theory is closely related to recursion theory in mathematical logic.[6] The study of abstract mathematical machines, known as automata, is the focus of automata theory, and these machines are categorized based on the formal languages they can recognize.[7] Computability theory investigates the degree to which a computer can solve a given problem.[4]

References

  1. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: : <blockquote> "central areas of the theory of computation: automata, computability, and complexity."</blockquote> (original not read by us) en.wikipedia.org
  2. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: Hodges, "Alan Turing: The Enigma", Princeton University Press, 2012; Rabin, "Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View", June 2012; Donald Monk, "Mathematical Logic", Springer-Verlag, 1976 (we also read that source) en.wikipedia.org
  3. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: Chomsky, "Three models for the description of language", IEEE Transactions on Information Theory, 1956, p. 113–124 (original not read by us) en.wikipedia.org
  4. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: Alan Turing, "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 1937, p. 230–265 (original not read by us) en.wikipedia.org
  5. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: Henry Gordon Rice, "Classes of Recursively Enumerable Sets and Their Decision Problems", Transactions of the American Mathematical Society, 1953, p. 358–366 (original not read by us) en.wikipedia.org
  6. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: Martin Davis, "The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed)", Dover Publications, 2004 (original not read by us) en.wikipedia.org
  7. Wikipedia, "Theory of computation" (CC BY-SA 4.0), which cites: Hopcroft, John E. and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation. 3rd ed", Reading, MA: Addison-Wesley., 2006 (we also read that source) en.wikipedia.org

Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Theory of computation (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.

More in Complexity Theory

Theoretical computer sciencePushdown automatonSorting algorithmQuicksortSearch algorithmString-searching algorithmPrim's algorithmPush–relabel maximum flow algorithmSimplex algorithmShortest path problemTravelling salesman problemNP (complexity)

Sources

Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.

Spotted an error? Know more?

Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced

Comments

Loading…
Open in the interactive codex →