Calculable number

A real number is referred to as a calculable number if there is a calculation rule that can provide approximations to any given accuracy. In particular, there are non-calculable numbers.

definition

A real number is called computable if there is a computable function that assigns a rational number to every natural number such that . ${\ displaystyle r}$ ${\ displaystyle i}$ ${\ displaystyle q}$ ${\ displaystyle \ left | rq \ right | <{\ frac {1} {i}}}$

Examples and characteristics

All real algebraic numbers are calculable, but also many transcendent numbers, e.g. B. the circle number or Euler's number . ${\ displaystyle \ pi}$ ${\ displaystyle \ mathrm {e}}$

An example of a non-calculable number is the hold number. The hold number is defined as the binary number between 0 and 1 whose -th place after the decimal point indicates whether a Turing machine with Gödel number terminates (1) or not (0) for the input . The holding number can not be calculated because the halting problem is undecidable . ${\ displaystyle i}$ ${\ displaystyle i}$ ${\ displaystyle i}$

Since every program of a Turing machine is finite and only consists of a finite number of characters, there are only countably many such programs and therefore only countably many calculable numbers. Since, as you can easily imagine, the sum and the product of two calculable numbers can be calculated again, and the inverse of every calculable number can also be calculated again, the calculable numbers form a subfield of the real numbers.

literature

Alan Turing : On Computable Numbers, with an Application to the Decision Problem . In: Proceedings of the London Mathematical Society . tape 42 , 1937, pp. 230-265 , doi : 10.1112 / plms / s2-42.1.230 .
Alan Turing: On Computable Numbers, with an Application to the Decision Problem. A correction . In: Proceedings of the London Mathematical Society . tape 43 , 1938, pp. 544-546 , doi : 10.1112 / plms / s2-43.6.544 .
Ernst Specker : Theorems of Analysis which cannot be proven constructively . In: The Journal of Symbolic Logic . tape 14 , no. 3 , 1949, pp. 145-158 , doi : 10.2307 / 2267043 .
Klaus Weihrauch : Computable analysis: an introduction . Springer, Berlin 2000, ISBN 3-540-66817-9 .
Roger Penrose : Computer Thinking . Spektrum Verlag, Heidelberg 2002, ISBN 3-89330-708-7 .