About: Theory of computation

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Theory of computation Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Organisation, within Data Space : el.dbpedia.org associated with source document(s)

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?".

Attributes	Values
rdf:type	Thing organisation
rdfs:label	Theory of computation (en)
rdfs:comment	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?". (en)
differentFrom	Computational theory of mind
sameAs	Theory of computation Theory of computation
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Distinguish dbt:For dbt:Main dbt:Reflist dbt:Short_description dbt:Isbn dbt:Computer_science dbt:Areas_of_mathematics
Subject	Theory of computation
gold:hypernym	Branch
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Theory_of_computation?oldid=1055726602&ns=0
Wikipage page ID	30402 (xsd:integer)
page length (characters) of wiki page	18208 (xsd:nonNegativeInteger)
Wikipage revision ID	1055726602 (xsd:integer)
has abstract	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?". 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Theory_of_computation
is differentFrom of	Computational theory of mind
is Wikipage redirect of	Theory of Computation History of theory of computation Theory of algorithms Computation Theory Computation theory Computational theorist Computational theory Computer theory
is Link from a Wikipage to another Wikipage of	Formal science Logic Logic in computer science Mark Jerrum Nondeterministic algorithm Nondeterministic finite automaton 20th century Abstract machine Alan Turing Alexander Razborov Alexey Lyapunov Algorithm Algorithmic information theory Algorithmic technique Algorithmically random sequence Algorithms Unlocked Alistair Sinclair Andrew Yao Artificial intelligence Arun Sharma (Indian Australian professor) Automata theory Bachelor of Computer Science BioData Mining Blum–Shub–Smale machine Boris Trakhtenbrot Moore machine Branches of science Categorical abstract machine General topology Generalized nondeterministic finite automaton German Informatics Society Glossary of areas of mathematics Glossary of artificial intelligence Glossary of computer science Jack Lutz Juris Hartmanis Dimiter Skordev Discovery science Discrete system Dondușeni District History of artificial intelligence History of computing hardware Jeffrey Ullman Jewish culture Jill Zimmerman Oded Goldreich Chinese room Khoury College of Computer Sciences List of Carnegie Mellon University people List of fields of doctoral studies in the United States List of inventions and discoveries by women List of mathematical functions List of mathematical theories List of people from Massachusetts List of pioneers in computer science Cognitive science Collatz conjecture Combinatorics, Probability and Computing Computability Computability theory Computable function Computation Computational semiotics Computer Computer science Computer science and engineering Computer scientist

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software