FACTOID # 12: It's not the government they hate: Washington DC has the highest number of hate crimes per capita in the US.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Computable number

In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. Equivalent definitions can be given using μ-recursive functions, Turing machines or λ-calculus as the formal representation of algorithms. The computable numbers form a real closed field and can be used in the place of real numbers for many, but not all, mathematical purposes. For other meanings of mathematics or math, see mathematics (disambiguation). ... Computer science (informally, CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Please refer to Real vs. ... In mathematics, computing, linguistics and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... In mathematical logic and computer science, lambda calculus, also λ-calculus, is a formal system designed to investigate function definition, function application, and recursion. ... In mathematics, a real closed field is an ordered field F in which any of the following equivalent conditions are true: Every non-negative element of F has a square root in F, and any polynomial of odd degree with coefficients in F has at least one root in F...

Contents

Formal definition

A real number a is said to be computable if it can be approximated by some computable function in the following manner: given any integer n ge 1, the function produces an integer k such that: In mathematics, the real numbers may be described informally in several different ways. ... It has been suggested that recursive function be merged into this article or section. ... The integers are commonly denoted by the above symbol. ...

{(k-1)over n} leq a leq {(k+1)over n}.

There are two similar definitions that are equivalent:

  • There exists a computable function which, given any positive rational error bound ε, produces a rational number r such that |r - a| leq epsilon.
  • There is a computable sequence of rational numbers qi converging to r such that |q_i - q_{i+1}| < 2^{-i}, for each i.

There is another equivalent definition of computable numbers via computable Dedekind cuts. A computable Dedekind cut is a computable function D; which when provided with a rational number r as input returns D(r)=true; or D(r)=false;, satisfying the following conditions: In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In mathematics, a Dedekind cut, named after Richard Dedekind, in a totally ordered set S is a partition of it, (A, B), such that A is closed downwards (meaning that for all a in A, x ≤ a implies that x is in A as well) and B is closed upwards...

exists r D(r)=mathit{true};
exists r D(r)=mathit{false};
(D(r)=mathit{true}) wedge (D(s)=mathit{false}) Rightarrow r<s;
D(r)=mathit{true} Rightarrow exist s>r, D(s)=mathit{true};

An example is given by a program D that defines the cube root of 3. Assuming q>0; this is defined by:

p^3<3 q^3 Rightarrow D(p/q)=mathit{true};
p^3>3 q^3 Rightarrow D(p/q)=mathit{false};

A real number is computable if and only if there is a computable Dedekind cut D converging to it. The function D is unique for each computable number (although of course two different programs may provide the same function).


A complex number is called computable if its real and imaginary parts are computable. In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ...


Properties

Although the set of real numbers is uncountable, the set of computable numbers is countable and thus most real numbers are not computable. The computable numbers can be counted by assigning a Gödel number to each Turing machine definition. This gives a function from the naturals to the computable reals. Although the computable numbers are an ordered field, the set of Gödel numbers corresponding to computable numbers is not itself computably enumerable, because it is not possible to effectively determine which Gödel numbers correspond to Turing machines that produce computable reals (this problem is in Turing degree 0ˈˈ ). Thus Cantor's diagonal argument cannot be used to produce uncountably many computable reals; at best, the reals formed from this method will be uncomputable. In mathematics, an uncountable set is a set which is not countable. ... In mathematics the term countable set is used to describe the size of a set, e. ... This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input â€” typically an integer or a tuple of integers or a sequence of characters â€” eventually halts if and... In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ... Cantors diagonal argument is a proof devised by Georg Cantor to demonstrate that the real numbers are not countably infinite. ...


The arithmetical operations on computable numbers are themselves computable in the sense that whenever real numbers a and b are computable then the following real numbers are also computable: a + b, a - b, ab, and a/b if b is nonzero. These operations are actually uniformly computable; for example, there is a Turing machine which on input (A,B,ε) produces output r, where A is the description of a Turing machine approximating a, B is the description of a Turing machine approximating b, and r is an ε approximation of a+b.


It is known that the least upper bound of a bounded increasing computable sequence of computable real numbers need not be a computable real number; this can be seen as evidence that the set of computable numbers is not robust enough for a development of calculus and differential equations.


The order relation on the computable numbers is not computable. There is no Turing machine which on input A (the description of a Turing machine approximating the number a) outputs "YES" if a > 0 and "NO" if a le 0. The reason: suppose the machine described by A keeps outputting 0 as ε approximations. It is not clear how long to wait before deciding that the machine will never output an approximation which forces a to be positive. Thus the machine will eventually have to guess that the number will equal 0, in order to produce an output; the sequence may later become different from 0. This idea can be used to show that the machine is incorrect on some sequences if it computes a total function. A similar problem occurs when the computable reals are represented as Dedekind cuts. In mathematics, a Dedekind cut, named after Richard Dedekind, in a totally ordered set S is a partition of it, (A, B), such that A is closed downwards (meaning that for all a in A, x ≤ a implies that x is in A as well) and B is closed upwards...


Every computable number is definable, but not vice versa. There are many definable, noncomputable real numbers: A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (in the von Neumann universe V). ...

  • The binary representation of the Halting problem (or any other uncomputable set of natural numbers).
  • Chaitin's constant, Ω, which is a real number Turing equivalent to the Halting problem.

It can be seen that a real number is computable if and only if the set of natural numbers it represents (when written in binary and viewed as a characteristic function) is computable. In the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. ... Turing equivalence may refer to: Turing equivalence (theory of computation) Turing equivalence (recursion theory) Category: ...


Computing digit strings

Turing's original paper defined computable numbers as follows:

A real number is computable if its digit sequence can be produced by some algorithm or Turing machine. The algorithm takes an integer n ge 1 as input and produces the n-th digit of the real number's decimal expansion as output.

Turing was aware that this definition is equivalent to the ε-approximation definition given above. The argument proceeds as follows: if a number is computable in the Turing sense, then it is also computable in the ε sense: if n > log10(1 / ε), then the first n digits of a provide an ε approximation of a. For the converse, we pick an ε computable real number a and distinguish two cases. If a is rational, then a is also Turing computable, since the digit expansions of rational numbers are eventually periodic and can therefore be produced by simple algorithms. If a is not rational, then it is possible to compute ever more precise ε-approximations until the nth digit is certain. This will eventually happen because a is not rational and thus the decimal expansion cannot be eventually constant.


There is no algorithm which takes as input the description of a Turing machine which produces ε approximations for the computable number a, and produces as output a Turing machine which enumerates the digits of a in the sense of Turing's definition. So while the two definitions are equivalent, they are not "computably equivalent".


An important property of Turing's definition is that the arithmetic operations are not uniformly computable in this representation. This can be seen most easily with addition: when adding decimal numbers, in order to produce one digit is may be necessary to look arbitrarily far to the right to determine if there is a carry to the current location. It is true, however, that if two real numbers have representations according to Turing's definitions then so will their sum, product, difference, and quotient. This lack of uniformity is one reason that the contemporary definition of computable numbers uses ε approximations rather than decimal expansions.


Can computable numbers be used instead of the reals?

The computable numbers include many of the specific real numbers which appear in practice, including all algebraic numbers, as well as e, π, and many other transcendental numbers. The question naturally arises of whether it is possible to dispose of the full set of reals and use computable numbers for all of mathematics. This idea is appealing from a constructivist point of view, and has been pursued by what Bishop and Richman call the Russian school of constructive mathematics. Because the set of computable numbers is not closed under basic operations such as taking the supremum of a bounded sequence, this set cannot be used as a replacement for the full set of real numbers in classical mathematics. In mathematics, an algebraic number is any number that is a root of an algebraic equation, a non-zero polynomial with integer (or equivalently, rational) coefficients. ... In mathematics, a transcendental number is any complex number that is not algebraic, that is, not the solution of a non-zero polynomial equation with integer (or, equivalently, rational) coefficients. ... In the philosophy of mathematics, constructivism asserts that it is necessary to find (or construct) a mathematical object to prove that it exists. ... Errett Albert Bishop (1928-1983) was an American mathematician known for is work on analysis. ...


References

  • Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics (Oxford, 1987).
  • Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. online version. Computable numbers (and Turing machines) were introduced in this paper.

Computable numbers were defined independently by Turing, Post and Church. See The Undecidable, ed. Martin Davis, for further original papers. Alan Turing is often considered the father of modern computer science. ...


See also


  Results from FactBites:
 
Computable number - Wikipedia, the free encyclopedia (1350 words)
In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the subset of the real numbers consisting of the numbers which can be computed by a finite, terminating algorithm.
The computable numbers form a real closed field and can be used in the place of real numbers for many, but by no means all, mathematical purposes.
There are however many real numbers which are not computable: the set of all computable numbers is countable (because the set of algorithms is) while the set of real numbers is not (see Cantor's diagonal argument).
Wikipedia:WikiProject Numbers - Wikipedia, the free encyclopedia (3828 words)
It is a prime number, a Mersenne prime, a Fermat prime, a permutable prime, a palindromic prime, a composite number, a highly composite number, an abundant number, a surreal number, and an amicable number with 0.
It is the Xth prime number, the previous being Number N - 2x, with which it comprises a twin prime, the next being [[Number N + 2x]], with which it comprises a twin prime.
User:Egil's proposal for naming the articles Number N (number), and making the spelled out names of the numbers be redirects, (e.g, Four hundred and ninety-six redirects to 496 (number)), received the most votes, and with the initiative of User:Dysprosia, the articles were moved accordingly.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m