Computable real number is a number, which can be produced to an arbitrary accuracy by a Turing computer, which by definition has a finite number of internal states, has input which is natural number and produces output which is natural numbers. Turing computer computes values of a function from natural numbers to itself by applying a recursive algorithm.
The following three formal definitions of the notion are equivalent.
- The number a is computable, if it can be expressed in terms of a computable function n→ f(n) from natural numbers to natural numbers characterized by the property
(f(n)-1)/n≤ a≤ (f(n)+1)/n .
For rational a=q, f(n)= nq satisfies the conditions. Note that this definition does not work for p-adic numbers since they are not well-ordered.
- The number a is computable if for an arbitrarily small rational number ε there exists a computable function producing a rational number r satisfying |r-x|≤ ε. This definition works also for p-adic numbers since it involves only the p-adic norm which has values which are powers of p and is therefore real valued.
- The number a is computable if there exists a computable sequence of rational numbers ri converging to a such that |a-ri| ≤ 2-i holds true. This definition works also for 2-adic numbers and its variant obtained by replacing 2 with the p-adic prime p makes sense for p-adic numbers.
- Rc is enumerable and therefore can be mapped to a subset of rationals: even the ordering can be preserved. Also Qp,c is enumerable but now one cannot speak of ordering. As a consequence, most real (p-adic) numbers are non-computable. Note that the pinary expansion of a rational is periodic after some pinary digit. For a p-adic transcendental this is not the case.
- Algebraic numbers are computable so that one can regard Rc as a kind of completion of algebraic numbers obtained by adding computable reals. For instance, π and e are computable. 2π can be computed by replacing the unit circle with a regular polygon with n sides and estimating the length as nLn. Ln the length of the side. e can be computed from the standard formula. Interestingly, ep is an ordinary p-adic number. An interesting question is whether there are other similar numbers. Certainly many algebraic numbers correspond to ordinary p-adic numbers.
- Rc (Qp,c) is a number field since the arithmetic binary operations +, -, ×, / are computable. Also differential and integral calculus can be constructed. The calculation of a derivative as a limit can be carried out by restricting the consideration to computable reals and there is always a computable real between two computable reals. Also Riemann sum can be evaluated as a limit involving only computable reals.
- An interesting distinction between real and p-adic numbers is that in the sum of real numbers the sum of arbitrarily high digits can affect even all lower digits so that it requires computational work to predict the outcome. For p-adic numbers memory digits affect only the higher digits. This is why p-adic numbers are tailor made for computational purposes. Canonical identification ∑ xnpn → ∑ xnp-n used in p-adic mass calculations to map p-adic mass squared to its real counterpart (see this) maps p-adics to reals in a continuous manner. For integers this corresponds is 2-to-1 due to the fact that the p-adic numbers -1= (p-1)/(1-p) and 1/p are mapped to p.
- For computable numbers, one cannot define the relation =. One can only define equality in some resolution ε. The category theoretical view about equality is also effective and conforms with the physical view.
Also the relations ≤ and ≥ fail to have computable counterparts since only the absolute value |x-y| can appear in the definition and one loses the information about the well-ordered nature of reals. For p-adic numbers there is no well-ordering so that nothing is lost. A restriction to non-equal pairs however makes order relation computable. For p-adic numbers the same is true.
- Computable number is obviously definable but there are also definanable numbers, which are not computable. Examples are Gödel numbers in a given coding scheme for statements, which are true but not provable. More generally, the Gödel numbers coding for undecidable problems such as the halting problem are uncomputable natural numbers in a given coding scheme. Chaitin's constant, which gives the probability that random Turing computation halts, is a non-computable but definable real number.
- Computable numbers are arithmetic numbers, which are numbers definable in terms of first order logic using Peano's axioms. First order logic does not allow statements about statements and one has an entire hierarchy of statements about... about statements. The hierarchy of infinite primes defines an analogous hierarchy in the TGD framework and is formally similar to a hierarchy of second quantizations (see this).
For a summary of earlier postings see Latest progress in TGD.
Post a Comment