Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Theory of computation

From Wikipedia, the free encyclopedia
Academic subfield of computer science
Not to be confused withComputational theory of mind.
For the journal, seeTheory of Computing.

Intheoretical computer science andmathematics, thetheory of computation is the branch that deals with what problems can be solved on a model of computation using analgorithm, howefficiently they can be solved and to what degree (e.g.,approximate solutions versus precise ones). The field is divided into three major branches:automata theory andformal languages,computability theory, andcomputational complexity theory, which are linked by the question:"What are the fundamental capabilities and limitations of computers?".[1]

In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called amodel of computation. There are several models in use, but the most commonly examined is theTuring machine.[2] 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 (seeChurch–Turing thesis).[3] It might seem that the potentially infinite memory capacity is an unrealizable attribute, but anydecidable problem[4] 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

[edit]

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 separated from mathematics and became an independent academic discipline with its own conferences such asFOCS in 1960 andSTOC in 1969, and its own awards such as theIMU Abacus Medal (established in 1981 as the Rolf Nevanlinna Prize), theGödel Prize, established in 1993, and theKnuth Prize, established in 1996.

Some pioneers of the theory of computation wereRamon Llull,Alonzo Church,Kurt Gödel,Alan Turing,Stephen Kleene,Rózsa Péter,John von Neumann andClaude Shannon.

Branches

[edit]

Automata theory

[edit]
Main article:Automata theory
GrammarLanguagesAutomatonProduction rules (constraints)
Type-0Recursively enumerableTuring machineα→β{\displaystyle \alpha \rightarrow \beta } (no restrictions)
Type-1Context-sensitiveLinear-bounded non-deterministic Turing machineαAβ→αγβ{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }
Type-2Context-freeNon-deterministicpushdown automatonA→γ{\displaystyle A\rightarrow \gamma }
Type-3RegularFinite-state automatonA→a{\displaystyle A\rightarrow a}
and
A→aB{\displaystyle A\rightarrow 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 toformal language theory,[5] 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

[edit]
Main article:Formal language
The Chomsky hierarchy
Set inclusions described by the Chomsky hierarchy

Formal language theory is a branch of mathematics concerned with describing languages as a set of operations over analphabet. 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, i.e.Chomsky hierarchy,[6] 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

[edit]
Main article:Computability theory

Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer. The statement that thehalting problem cannot be solved by a Turing machine[7] 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 wasRice's theorem, which states that for all non-trivial properties of partial functions, it isundecidable whether a Turing machine computes a partial function with that property.[8]

Computability theory is closely related to the branch ofmathematical logic calledrecursion theory, which removes the restriction of studying only models of computation which are reducible to the Turing model.[9] Many mathematicians and computational theorists who study recursion theory will refer to it as computability theory.

Computational complexity theory

[edit]
Main article:Computational complexity theory
A representation of the relation among complexity classes

Computational 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 andspace complexity, which are respectively how many steps it takes to perform a computation, and how much memory is required to perform that computation.

In order to analyze how much time and space a givenalgorithm 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 aren 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 we're seeking. We thus say that in order to solve this problem, the computer needs to perform a number of steps that grow linearly in the size of the problem.

To simplify this problem, computer scientists have adoptedbigO notation, which allows functions to be compared in a way that ensures that particular aspects of a machine's construction do not need to be considered, but rather only theasymptotic behavior as problems become large. So in our previous example, we might say that the problem requiresO(n){\displaystyle O(n)} steps to solve.

Perhaps the most important open problem in all ofcomputer science is the question of whether a certain broad class of problems denotedNP can be solved efficiently. This is discussed further atComplexity classes P and NP, andP versus NP problem is one of the sevenMillennium Prize Problems stated by theClay Mathematics Institute in 2000. The Official Problem Description was given byTuring Award winnerStephen Cook.

Models of computation

[edit]
Main article:Model of computation

Aside from a Turing machine, other equivalent (see Church–Turing 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 ofBeta reduction.
Combinatory logic
is a concept which has many similarities toλ{\displaystyle \lambda }-calculus, but also important differences exist (e.g. fixed point combinatorY 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 mu-recursive function,i.e. its defining sequence, any input value(s) and a sequence of recursive functions appearing in the defining sequence with inputs and outputs. Thus, if in the defining sequence of a recursive functionf(x){\displaystyle f(x)} the functionsg(x){\displaystyle g(x)} andh(x,y){\displaystyle h(x,y)} appear, then terms of the form 'g(5)=7' or 'h(3,2)=10' might appear. Each entry in this sequence needs to be an application of a basic function or follow from the entries above by usingcomposition,primitive recursion orμ recursion. For instance iff(x)=h(x,g(x)){\displaystyle f(x)=h(x,g(x))}, then for 'f(5)=3' to appear, terms like 'g(5)=6' and 'h(5,6)=3' must occur above. The computation terminates only if the final term gives the value of the recursive function applied to the inputs.
Markov algorithm
astring rewriting system that usesgrammar-like rules to operate onstrings 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), e.g. 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 withGödel numbering techniques: the fact that each register holds a natural number allows the possibility of representing a complicated thing (e.g. a sequence, or a matrix etc.) by an appropriately huge natural number — unambiguity of both representation and interpretation can be established bynumber 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 toprogramming languages. Another formalism mathematically equivalent to regular expressions,finite automata are used in circuit design and in some kinds of problem-solving.Context-free grammars specify programming language syntax. Non-deterministicpushdown automata are another formalism equivalent to context-free 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 offormal languages that the model can generate; in such a way to theChomsky hierarchy of languages is obtained.

References

[edit]
  1. ^Sipser (2013, p. 1):

    "central areas of the theory of computation: automata, computability, and complexity."

  2. ^Hodges, Andrew (2012).Alan Turing: The Enigma (The Centenary ed.).Princeton University Press.ISBN 978-0-691-15564-7.
  3. ^Rabin, Michael O. (June 2012).Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.
  4. ^Donald Monk (1976).Mathematical Logic. Springer-Verlag.ISBN 9780387901701.
  5. ^Hopcroft, John E. andJeffrey D. Ullman (2006).Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley.ISBN 978-0-321-45536-9.
  6. ^Chomsky, N. (1956). "Three models for the description of language".IEEE Transactions on Information Theory.2 (3):113–124.Bibcode:1956IRTIT...2..113C.doi:10.1109/TIT.1956.1056813.S2CID 19519474.
  7. ^Alan Turing (1937)."On computable numbers, with an application to the Entscheidungsproblem".Proceedings of the London Mathematical Society.2 (42). IEEE:230–265.Bibcode:1937PLMS...42..230T.doi:10.1112/plms/s2-42.1.230.S2CID 73712. Retrieved6 January 2015.
  8. ^Henry Gordon Rice (1953)."Classes of Recursively Enumerable Sets and Their Decision Problems".Transactions of the American Mathematical Society.74 (2). American Mathematical Society:358–366.doi:10.2307/1990888.JSTOR 1990888.
  9. ^Martin Davis (2004).The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications.ISBN 978-0486432281.

Further reading

[edit]
Textbooks aimed at computer scientists

(There are many textbooks in this area; this list is by necessity incomplete.)

Books on computability theory from the (wider) mathematical perspective
Historical perspective

External links

[edit]
Majormathematics areas
Foundations
Algebra
Analysis
Discrete
Geometry
Number theory
Topology
Applied
Computational
Related topics
Note: This template roughly follows the 2012ACM Computing Classification System.
Hardware
Computer systems organization
Networks
Software organization
Software notations andtools
Software development
Theory of computation
Algorithms
Mathematics ofcomputing
Information systems
Security
Human-centered computing
Concurrency
Artificial intelligence
Machine learning
Graphics
Applied computing
Specialized PlatformDevelopment
Retrieved from "https://en.wikipedia.org/w/index.php?title=Theory_of_computation&oldid=1330481634"
Category:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp