Concept
Theory of computation
Overview
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 (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. Several models exist for this purpose, such as 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.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
The arbitrarily large event with which the series starts has no importance at all. We can arbitrarily exclude any set of events at the big end of an abstractive set without the loss of any important property to the set as thus modified. I call the limiting character of natural relations which is indicated by an abstractive set, the 'intrinsic character' of the set; also the properties, connected with the relation of…
Alfred North Whitehead, The Concept of Nature The Tarner Lectures Delivered in Trinity College, November 1919
States what Theory of computation is.
The notion of continuity depends upon that of _order_, since continuity is merely a particular type of order. Mathematics has, in modern times, brought order into greater and greater prominence. In former days, it was supposed (and philosophers are still apt to suppose) that quantity was the fundamental notion of mathematics.
Bertrand Russell, Mysticism and Logic and Other Essays
States what Theory of computation is.
Please remember that the names are technical names, meant, no doubt, to be suggestive, but used in strictly defined senses. We have suffered much from critics who consider it sufficient to criticise our procedure on the slender basis of a knowledge of the dictionary meanings of such terms. For example, a one-to-one correlation depends on the notion of a class with only one member, and this notion is defined without…
Alfred North Whitehead, The organisation of thought, educational and scientific
States what Theory of computation is.
Philosophers who discussed Theory of computation
Related ideas
- Automata theory
- Formal language
- Alan Turing
- Princeton University Press
- Grammar
- Computability theory
- John von Neumann
- Kurt Gödel
- Lambda calculus
- Mathematics
- Mathematical logic
- Number theory
- Abstraction
- Turing machine
- Theoretical computer science
- Alonzo Church
- Computer science
- Context-free grammar
- Church–Turing thesis
- Ramon Llull
- Algorithm
- Decidability (logic)
- P versus NP problem
- Primitive recursive function
Place in the tradition
Part of Philosophy of computer science.