Theory of computation
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 or to what degree (e.g., approximate solutions versus precise ones). 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?".
- Comment
- enIn 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 or to what degree (e.g., approximate solutions versus precise ones). 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?".
- Depiction
- DifferentFrom
- Computational theory of mind
- Has abstract
- enIn 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 or to what degree (e.g., approximate solutions versus precise ones). 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). 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 finite amount of memory.
- Hypernym
- Branch
- Is primary topic of
- Theory of computation
- Label
- enTheory of computation
- Link from a Wikipage to an external page
- www.cis.upenn.edu/~giorgi/cl.html
- cse.ucdenver.edu/~cscialtman/foundation/Essentials%20of%20Theoretical%20Computer%20Science.pdf
- toc.csail.mit.edu/
- toc.seas.harvard.edu/
- www.claymath.org/sites/default/files/pvsnp.pdf
- www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
- web.archive.org/web/20070107040625/http:/www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
- Link from a Wikipage to another Wikipage
- Alan Turing
- Algorithm
- Algorithmic efficiency
- Alonzo Church
- Alphabet (formal languages)
- Approximation algorithms
- Asymptotic analysis
- Automata theory
- Beta reduction
- Big O notation
- Carl Herbert Smith
- Category:Theory of computation
- Chomsky hierarchy
- Church–Turing thesis
- Claude Shannon
- Clay Mathematics Institute
- Combinatory logic
- Computability theory
- Computational complexity theory
- Computer science
- Context-free grammar
- Context-sensitive grammar
- Decidability (logic)
- File:Chomsky-hierarchy.svg
- File:Complexity subsets pspace.svg
- File:Maquina.png
- Finite state automaton
- Finite state machines
- Formal language
- Function composition (computer science)
- Gödel numbering
- Grammar
- Halting problem
- Hartley Rogers, Jr
- Harvard
- Introduction to Automata Theory, Languages, and Computation
- Jeffrey D. Ullman
- John Hopcroft
- John von Neumann
- Kurt Gödel
- Lambda calculus
- Linear bounded automaton
- Markov algorithm
- Martin Davis (mathematician)
- Massachusetts Institute of Technology
- Mathematical logic
- Mathematics
- Millennium Prize Problems
- Model of computation
- NP (complexity)
- Number theory
- P = NP problem
- Primitive recursion
- Primitive recursive function
- Programming language
- Program semantics
- Pushdown automaton
- P versus NP problem
- Quantification theory
- Ramon Llull
- Recursion theory
- Recursively enumerable language
- Register machine
- Regular expressions
- Regular grammar
- Rice's theorem
- Richard L. Epstein
- Rózsa Péter
- Stephen Cook
- Stephen Kleene
- String (computer science)
- String rewriting system
- Theoretical computer science
- Turing Award
- Turing machine
- Walter A. Carnielli
- Μ-recursive function
- SameAs
- 4zunp
- Algoritmalar teorisi
- Beräkningsteori
- Konputazioaren teoria
- Laskettavuus
- m.07h44
- Q844718
- Teória algoritmov
- Teoria computației
- Teoria da computação
- Teoría da computación
- Teoria de la computació
- Teoría de la computación
- Teoría de la computación
- Teoria della computazione
- Teoria obliczeń
- Teorija računanja
- Teorija računanja
- Teorija računanja
- Teori komputasi
- Teorio de komputado
- Teori pengiraan
- Teorya ng komputasyon
- Theory of computation
- Theory of computation
- Θεωρία υπολογισμού
- Назарияи муҳосибот
- Теория алгоритмов
- Теорија израчунљивости
- Теорія алгоритмів
- نظرية الحوسبة
- نظریه محاسبات
- نظریہ کمپیوٹیشن
- अभिकलन का सिद्धांत
- ทฤษฎีการคำนวณ
- 計算理論
- 计算理论
- 계산 이론
- Subject
- Category:Theory of computation
- Thumbnail
- WasDerivedFrom
- Theory of computation?oldid=1108170363&ns=0
- WikiPageLength
- 18232
- Wikipage page ID
- 30402
- Wikipage revision ID
- 1108170363
- WikiPageUsesTemplate
- Template:Areas of mathematics
- Template:Cite book
- Template:Computer science
- Template:Distinguish
- Template:For
- Template:Isbn
- Template:Main
- Template:Reflist
- Template:Short description
