FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Computation theory

Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. Computability theory addresses four main questions:

• What problems can Turing machines solve?
• What other systems are equivalent to Turing machines?
• What problems require more powerful machines?
• What problems can be solved by less powerful machines?

See the article on theory of computation for a chart showing which classes of problems are subsets of other classes.

 Contents

## What problems can Turing machines solve? GA_googleFillSlot("encyclopedia_square");

Not all problems can be solved. An undecidable problem is one that cannot be solved by any algorithm, even given unbounded time and memory. Many undecidable problems are known. For example, the Entscheidungsproblem (German for "decision problem") is this: given a statement in first-order predicate calculus, decide whether it is universally valid. Church and Turing independently proved this is undecidable. The halting problem is: given a program and inputs for it, decide whether it will run forever or will eventually halt. Turing proved this is also undecidable. A computable number is a real number which can be approximated to any arbitrary degree of accuracy by an algorithm. Turing proved that almost all numbers are uncomputable. Chaitin's constant is an uncomputable number, even though it is well defined.

## What other systems are equivalent to Turing machines?

The languages that are accepted by a Turing machine are exactly those that are generated by formal grammars. The lambda calculus is a way of defining functions. The functions that can be computed in the lambda calculus are exactly those that can be computed by a Turing machine. These three formulations, Turing machines, formal grammars, and the lambda calculus all look very different, and were all developed by different people. Yet they are all equivalent, and have the same problem-solving power. This is generally taken as evidence for the Church-Turing thesis, which is the claim that our intuitive notion of an algorithm or an effective procedure is captured by the mathematical definition of a Turing machine.

Electronic computers, and even quantum computers, are exactly equivalent to Turing machines, if they have access to an unbounded supply of memory. As a corollary, all implementable programming languages are at best equivalent in power to a Turing machine (in practice, a very few are less powerful). Such languages are said to be Turing-complete. Systems equivalent to a Turing machine include:

• Turing machine with several tapes
• Turing machine with a 2-dimensional "tape" (an infinite number of linear tapes)
• Turing machine with a limited number of states and tape symbols
• States symbols can be any of 2 18, 3 10, 4 6, 5 5, 7 4, 10 3, 22 2
• Turing machine with 2 states, always reversing (http://skelet.ludost.net/bb/RTM.htm) the tape value
• Turing machine with 2 states, with 3 possible value changes: 0->0, 0->1 and 1->1 (proposed by Hao Wang)
• Finite state machine with 2 stacks
• Finite state machine with 2 counters
• Formal grammar
• Post system
• Lambda calculus
• Partial recursive functions
• Almost any modern programming language (when given unlimited memory), including:
• A language with 1 instruction, 1 parameter, and 1 special memory location (URISC) or 1 instruction with 3 parameters (OISC), (see also [1] (http://www.catb.org/~esr/retro/))
• A language with 8 instructions, no parameters (see BrainFuck)
• Wang tiles
• Recurrent neural network (finite-precision inputs/outputs/weights, infinite-precision signals initialized to zero)
• Cellular automaton, including:
• Conway's Game of Life
• Cellular automaton with just 1 dimension, 2 states, 3 cells per neighborhood (e.g. rule 110)
• Non-deterministic Turing machine
• Probabilistic Turing Machine
• Quantum computer

The last three examples use a slightly different definition of accepting a language. They are said to accept a string if any computation accepts (for non-deterministic), or most computations accept (for probabilistic and quantum). Given these definitions, those machines have the same power as a Turing machine for accepting languages.

## What problems require more powerful machines?

Sometimes machines are considered that have more power than a Turing machine. For example, an oracle machine uses a black box that can compute some particular function that might not be possible for an ordinary Turing machine. The computational strength of an oracle machine is described by its Turing degree. The theory of real computation deals with machines using infinite-precision real numbers. Within this theory, it is possible to prove interesting statements such as "the complement of the Mandelbrot set is only partially decidable". For other such powerful machines, see super-Turing computation and hypercomputation.

Results from FactBites:

 Theory of computation - Wikipedia, the free encyclopedia (1029 words) Computability theory deals primarily with the question of whether a problem is solvable at all on a computer. The halting problem 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. Computability theory is closely related to the branch of mathematical logic called recursion theory, which removes the restriction of studying only models of computation which are close to physically realizable.
 Computation - Wikipedia, the free encyclopedia (238 words) However, the meaning of the word "computer" should be understood here in a large sense, since it does not apply only to digital computers. In computer science (which is sometimes described as the discipline that studies computations) and in mathematical logic, mathematical models of computers are defined; a typical model is the Turing machine. The sub-field of computer science which studies mathematical models of computations is called the theory of computation.
More results at FactBites »

Share your thoughts, questions and commentary here