Computable number

[5] Equivalent definitions can be given using μ-recursive functions, Turing machines, or λ-calculus as the formal representation of algorithms.

[citation needed] In the following, Marvin Minsky defines the numbers to be computed in a manner similar to those defined by Alan Turing in 1936;[6] i.e., as "sequences of digits interpreted as decimal fractions" between 0 and 1:[7] A computable number [is] one for which there is a Turing machine which, given n on its initial tape, terminates with the nth digit of that number [encoded on its tape].The key notions in the definition are (1) that some n is specified at the start, (2) for any n the computation only takes a finite number of steps, after which the machine produces the desired output and terminates.

An alternate form of (2) – the machine successively prints all n of the digits on its tape, halting after printing the nth – emphasizes Minsky's observation: (3) That by use of a Turing machine, a finite definition – in the form of the machine's state table – is being used to define what is a potentially infinite string of decimal digits.

, satisfying the following conditions: An example is given by a program D that defines the cube root of 3.

Assigning a Gödel number to each Turing machine definition produces a subset

There are only countably many Turing machines, showing that the computable numbers are subcountable.

This is because there is no algorithm to determine which Gödel numbers correspond to Turing machines that produce computable reals.

of machines representing computable reals, and Cantor's diagonal argument cannot be used constructively to demonstrate uncountably many of them.

, and therefore there exists a subset consisting of the minimal elements, on which the map is a bijection.

These operations are actually uniformly computable; for example, there is a Turing machine which on input (A,B,

The fact that computable real numbers form a field was first proved by Henry Gordon Rice in 1954.

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.

That is, there is a program that takes as input two Turing machines A and B approximating numbers

Every computable number is arithmetically definable, but not vice versa.

The set of computable real numbers (as well as every countable, densely ordered subset of computable reals without ends) is order-isomorphic to the set of rational numbers.

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.

computable real number a and generate increasingly precise approximations until the nth digit after the decimal point is certain.

Unless certain topological properties of the real numbers are relevant, it is often more convenient to deal with elements of

Note that this property of decimal expansions means that it is impossible to effectively identify the computable real numbers defined in terms of a decimal expansion and those defined in the

Hirst has shown that there is no algorithm which takes as input the description of a Turing machine which produces

In order to produce one digit, it may be necessary to look arbitrarily far to the right to determine if there is a carry to the current location.

This lack of uniformity is one reason why the contemporary definition of computable numbers uses

satisfying a universal formula may have an arbitrarily high position in the hyperarithmetic hierarchy.

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 the Russian school of constructive mathematics.

[13] Modern examples include the CoRN library (Coq),[14] and the RealLib package (C++).

[15] A related line of work is based on taking a real RAM program and running it with rational or floating-point numbers of sufficient precision, such as the iRRAM package.