Alan Turing
(1912–1954)British mathematician, who introduced the concept of the Turing machine.Born in London, he was educated at King's College, Cambridge, where he was elected to a fellowship in 1936. In the ...
algorithm
A documented series of steps which leads to the transformation of some data. For example, in order to calculate the sum of a series of numbers a possible algorithm would involve repeatedly adding the ...
artificial intelligence
The theory and development of computer systems able to perform tasks normally requiring human intelligence, such as visual perception, speech recognition, decision-making, and translation between ...
automaton
A general term for a device that mechanically processes an input string with the aim either of deciding whether it belongs to some set of strings (i.e. to a formal language) or of producing an output ...
cellular automaton
A mathematical model of self-replication and destruction, usually represented by a checkerboard of either fixed or infinite dimensions, each cell of which has a finite number of states, usually ...
Chomsky hierarchy
A series of four classes of formal languages whose definition in 1959 by Noam Chomsky marked the beginning of formal language theory, and that have ever since remained central to the subject. In ...
Church–Turing thesis
The proposition that the set of functions on the natural numbers that can be defined by algorithms is precisely the set of functions definable in one of a number of equivalent models of computation. ...
Church's thesis
The hypothesis, put forward by Alonzo Church in 1935, that any function on the natural numbers that can be computed by an algorithm can be defined by a formula of the lambda calculus. See also ...
complexity classes
A way of grouping algorithms, computable functions, or specifications according to their computational complexity. Computable functions that have the same complexity according to some measure are ...
complexity measure
A means of measuring the resources used during a computation. A general definition is contained in Blum's axioms. In the special case of Turing machines, during any Turing machine computation various ...
complexity theory
A conceptual framework that departs from the reductionism of scientific thinking by acknowledging that some of the most pressing and difficult problems facing humans early in the 21st century cannot ...
computability
A mathematical function determines a unique numerical output for any appropriate numerical input. A function is computable just if there is a procedure that can be carried out in a ...
computable function
A functionf : X → Yfor which there exists an algorithm for evaluating f(x) for any element x in the domain X of f.
computer
Any device capable of carrying out a sequence of operations in a defined manner. The definition of the operations is called the program. An analog computer performs computations by manipulating ...
functionalism
[Th]An approach that explains social phenomena in terms of their integrative relationships and contributions to the maintenance of society, or to the needs of individuals, rather than in terms of ...
Gödel's theorem
A fundamental result in mathematics stating that, in a given mathematical structure, some propositions cannot be proved to be true or false, i.e. the propositions are undecidable, using only the ...
halting problem
A decision problem that was discovered and investigated by Alan Turing in 1936. Suppose M is a Turing machine and let x be an input to M. If we start the machine running two things might happen: ...
lambda calculus
A formalism for representing functions and ways of combining functions, invented around 1930 by the logician Alonzo Church. The following are examples of λ-expressions:λx.x denotes the identity ...
machine
Usually, a real — or imagined — computer (see also virtual machine, abstract machine, Turing machine), which may or may not be sequential and deterministic. In formal language theory it may imply a ...
