38:
4724:
3136:. Though the computable reals exhaust those reals we can calculate or approximate, the assumption that all reals are computable leads to substantially different conclusions about the real 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
1751:
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
2664:
in the sense of Turing's definition. Similarly, it means that the arithmetic operations on the computable reals are not effective on their decimal representations as when adding decimal numbers. In order to produce one digit, it may be necessary to look arbitrarily far to the right to determine if
2043:
The computable real numbers do not share all the properties of the real numbers used in analysis. For example, the least upper bound of a bounded increasing computable sequence of computable real numbers need not be a computable real number. A sequence with this property is known as a
3172:
Computer packages representing real numbers as programs computing approximations have been proposed as early as 1985, under the name "exact arithmetic". Modern examples include the CoRN library (Coq), and the RealLib package (C++). A related line of work is based on taking a
1355:
that are defined in terms of it). This is because there is no algorithm to determine which Gödel numbers correspond to Turing machines that produce computable reals. In order to produce a computable real, a Turing machine must compute a
908:
1006:
3143:
To actually develop analysis over computable numbers, some care must be taken. For example, if one uses the classical definition of a sequence, the set of computable numbers is not closed under the basic operation of taking the
1222:
1131:
330:
2496:
3038:
2616:
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
801:
744:
229:
169:
This is however not the modern definition which only requires the result be accurate to within any given accuracy. The informal definition above is subject to a rounding problem called the
2284:
534:
1493:
into the natural numbers of the computable numbers, proving that they are countable. But, again, this subset is not computable, even though the computable reals are themselves ordered.
2552:
1759:
While the full order relation is not computable, the restriction of it to pairs of unequal numbers is computable. That is, there is a program that takes as input two Turing machines
688:
412:
3106:
638:
1959:
2052:
in 1949. Despite the existence of counterexamples such as these, parts of calculus and real analysis can be developed in the field of computable numbers, leading to the study of
2985:
2953:
2900:
4221:
4536:
4459:
4420:
4382:
4354:
4326:
4298:
4186:
4153:
4125:
4097:
2926:
2843:
360:
2870:
2807:
2780:
2721:
2611:
2437:
2378:
3073:
2683:
2654:
2634:
2336:
2312:
2231:
2211:
1979:
1906:
1741:
1603:
1559:
3238:
1717:
1044:
2160:
2113:. 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.
2099:
2034:
1886:
1831:
2005:
1857:
1691:
441:
571:
1439:
2180:
1805:
1785:
1661:
1483:
1463:
1393:
1353:
1329:
1305:
1277:
591:
461:
2753:
2584:
2410:
807:
914:
1628:
2213:-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
3511:
3337:
3872:
Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
3621:
2350:
but it may improperly end in an infinite sequence of 9's in which case it must have a finite (and thus computable) proper decimal expansion.
2665:
there is a carry to the current location. This lack of uniformity is one reason why the contemporary definition of computable numbers uses
1137:
4015:
3811:
1052:
2636:
approximation sense. Hirst has shown that there is no algorithm which takes as input the description of a Turing machine which produces
2136:
A real number is computable if its digit sequence can be produced by some algorithm or Turing machine. The algorithm takes an integer
4047:
252:
2959:(in addition to being totally disconnected). This leads to genuine differences in the computational properties. For instance the
17:
3980:
3653:
3615:
3555:
2353:
Unless certain topological properties of the real numbers are relevant, it is often more convenient to deal with elements of
4236:
147:
the computation only takes a finite number of steps, after which the machine produces the desired output and terminates.
4231:
2442:
2990:
750:
3999:
3957:
3715:
3438:
696:
1501:
The arithmetical operations on computable numbers are themselves computable in the sense that whenever real numbers
198:
3269:"Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators"
3177:
program and running it with rational or floating-point numbers of sufficient precision, such as the iRRAM package.
4191:
2236:
1307:
to the computable numbers. There are only countably many Turing machines, showing that the computable numbers are
4609:
466:
4687:
1235:
is unique for each computable number (although of course two different programs may provide the same function).
4753:
3497:
2501:
2060:
4748:
4570:
4007:
3156:, see the section above). This difficulty is addressed by considering only sequences which have a computable
1396:
643:
372:
3474:
3078:
596:
4040:
3137:
1911:
1400:
4196:
3201:
2962:
2931:
2878:
2810:
2586:
can only be bijectively (and homeomorphically under the subset topology) identified with the subset of
2109:
Both of these examples in fact define an infinite set of definable, uncomputable numbers, one for each
3592:
3120:
The computable numbers include the specific real numbers which appear in practice, including all real
2063:, but not vice versa. There are many arithmetically definable, noncomputable real numbers, including:
162:
definition – in the form of the machine's state table – is being used to define what is a potentially
4604:
4560:
3109:
4202:
4727:
4599:
2110:
170:
4519:
4442:
4403:
4365:
4337:
4309:
4281:
4169:
4136:
4108:
4080:
2909:
2816:
345:
4033:
3273:
3196:
2848:
2785:
2758:
2699:
2589:
2415:
2356:
1442:
3822:
Turing, A. M. (1936). "On
Computable Numbers, with an Application to the Entscheidungsproblem".
3043:
2346:
th digit after the decimal point is certain. This always generates a decimal expansion equal to
1485:, and therefore there exists a subset consisting of the minimal elements, on which the map is a
92:
3772:
3157:
2668:
2639:
2619:
2321:
2297:
2216:
2196:
1964:
1891:
1726:
1588:
1544:
3968:
1696:
1022:
4672:
4508:
3331:
3133:
2956:
2139:
2084:
2078:
2010:
1862:
1810:
1332:
1984:
1836:
1670:
4425:
4158:
3528:
O’Connor, Russell (2008). "Certified Exact
Transcendental Real Number Computation in Coq".
3459:
3323:
3296:
3186:
2689:
419:
107:
and can be used in the place of real numbers for many, but not all, mathematical purposes.
31:
123:
in 1936; i.e., as "sequences of digits interpreted as decimal fractions" between 0 and 1:
8:
4636:
4546:
4503:
4485:
4263:
3473:
Boehm, Hans-J.; Cartwright, Robert; Riggle, Mark; O'Donnell, Michael J. (8 August 1986).
3224:
3161:
2072:
2053:
1617:
1372:
555:
193:
1421:
903:{\displaystyle (D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;}
4541:
4253:
3935:
3839:
3803:
3795:
3756:
3704:
3561:
3533:
3503:
3140:
point of view, and has been pursued by the
Russian school of constructive mathematics.
2165:
1790:
1770:
1743:
approximations. It is not clear how long to wait before deciding that the machine will
1646:
1490:
1468:
1448:
1378:
1338:
1314:
1290:
1262:
576:
446:
3944:
This paper describes the development of the calculus over the computable number field.
3852:"On Computable Numbers, with an Application to the Entscheidungsproblem: A correction"
3751:
3734:
3220:
2726:
2557:
2383:
1001:{\displaystyle D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;}
4699:
4662:
4626:
4565:
4551:
4246:
3995:
3976:
3953:
3721:
3711:
3649:
3611:
3551:
3493:
3287:
3268:
1621:
104:
3939:
3807:
3565:
3507:
4717:
4646:
4621:
4555:
4464:
4430:
4271:
4241:
4163:
4066:
3925:
3889:
3863:
3831:
3787:
3746:
3676:
3603:
3543:
3485:
3482:
Proceedings of the 1986 ACM conference on LISP and functional programming - LFP '86
3447:
3310:
Rogers, Hartley, Jr. (1959). "The present theory of Turing machine computability".
3282:
3191:
3153:
3149:
3121:
2755:
are essentially identical. Thus, computability theorists often refer to members of
2439:
can be identified with binary decimal expansions, but since the decimal expansions
2121:
2045:
1361:
4594:
4498:
4130:
3843:
3643:
3547:
3455:
3319:
3292:
2117:
2068:
1756:. The same holds for the equality relation: the equality test is not computable.
1280:
363:
100:
96:
1256:
4641:
4631:
4616:
4435:
4303:
4074:
3867:
3835:
3602:. Lecture Notes in Computer Science. Vol. 2064. Springer. pp. 30–47.
3264:
3228:
2693:
1357:
1239:
37:
4010:
converging to the singleton real. Other representations are discussed in §4.1.
3894:
3877:
3725:
1227:
A real number is computable if and only if there is a computable
Dedekind cut
85:
64:
that can be computed to within any desired precision by a finite, terminating
4742:
4704:
4677:
4586:
3768:
3699:
2903:
2102:
2049:
1365:
158:
th – emphasizes Minsky's observation: (3) That by use of a Turing machine, a
116:
3851:
3607:
3108:
satisfying a universal formula may have an arbitrarily high position in the
1631:, because the definition of a computable field requires effective equality.
544:
There is another equivalent definition of computable numbers via computable
88:
in 1912, using the intuitive notion of computability available at the time.
4667:
4469:
1753:
1308:
545:
119:
defines the numbers to be computed in a manner similar to those defined by
61:
45:
3930:
3913:
3489:
3436:
Kushner, Boris A. (2006). "The constructive mathematics of A. A. Markov".
127:
A computable number one for which there is a Turing machine which, given
103:
as the formal representation of algorithms. The computable numbers form a
4493:
4275:
2660:, and produces as output a Turing machine which enumerates the digits of
1407:
340:
182:
120:
53:
110:
4474:
4331:
3799:
3760:
3532:. Lecture Notes in Computer Science. Vol. 5170. pp. 246–261.
1418:
real numbers are not computable. Here, for any given computable number
1415:
1284:
339:
There exists a computable function which, given any positive rational
3691:
3681:
3451:
1486:
1411:
1242:
is called computable if its real and imaginary parts are computable.
1217:{\displaystyle p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;}
1016:
65:
3791:
1639:
The order relation on the computable numbers is not computable. Let
1509:
are computable then the following real numbers are also computable:
4582:
4513:
4359:
3174:
3145:
1126:{\displaystyle p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;}
3538:
3472:
4102:
4025:
3475:"Exact real arithmetic: A case study in higher order programming"
232:
2127:
2116:
The set of computable real numbers (as well as every countable,
1643:
be the description of a Turing machine approximating the number
4056:
3664:
3232:
2132:
Turing's original paper defined computable numbers as follows:
150:
An alternate form of (2) – the machine successively prints all
3312:
Journal of the
Society for Industrial and Applied Mathematics
325:{\displaystyle {f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.}
84:. The concept of a computable real number was introduced by
3393:
2902:
are sometimes called reals as well and though containing a
2342:
and generate increasingly precise approximations until the
2193:
Turing was aware that this definition is equivalent to the
2182:-th digit of the real number's decimal expansion as output.
27:
Real number that can be computed within arbitrary precision
3239:
Institute of
Mathematics of the Polish Academy of Sciences
3245:
2380:(total 0,1 valued functions) instead of reals numbers in
1533:; for example, there is a Turing machine which on input (
1283:
corresponding to the computable numbers and identifies a
3966:
2190:
only refers to the digits following the decimal point.)
3669:
Bulletin of the Polish
Academy of Sciences, Mathematics
335:
There are two similar definitions that are equivalent:
41:
3167:
154:
of the digits on its tape, halting after printing the
4522:
4445:
4406:
4368:
4340:
4312:
4284:
4205:
4172:
4139:
4111:
4083:
3081:
3075:
quantifier free, must be computable while the unique
3046:
2993:
2965:
2934:
2912:
2881:
2851:
2819:
2788:
2761:
2729:
2702:
2671:
2642:
2622:
2592:
2560:
2504:
2445:
2418:
2386:
2359:
2324:
2300:
2239:
2219:
2199:
2168:
2142:
2087:
2013:
1987:
1967:
1914:
1894:
1865:
1839:
1813:
1793:
1773:
1729:
1699:
1673:
1649:
1591:
1577:
is the description of a Turing machine approximating
1569:
is the description of a Turing machine approximating
1547:
1471:
1451:
1424:
1381:
1341:
1317:
1293:
1265:
1140:
1055:
1025:
917:
810:
753:
699:
646:
599:
579:
558:
469:
449:
422:
375:
348:
255:
201:
111:
Informal definition using a Turing machine as example
1752:
occurs when the computable reals are represented as
1634:
1259:
to each Turing machine definition produces a subset
139:
The key notions in the definition are (1) that some
3994:. Texts in Theoretical Computer Science. Springer.
3405:
1981:(approaching 0), one eventually can decide whether
416:There is a computable sequence of rational numbers
4530:
4453:
4414:
4376:
4348:
4320:
4292:
4215:
4180:
4147:
4119:
4091:
3918:Journal of the Association for Computing Machinery
3703:
3572:
3100:
3067:
3032:
2979:
2947:
2920:
2894:
2864:
2837:
2801:
2774:
2747:
2715:
2677:
2648:
2628:
2605:
2578:
2546:
2491:{\displaystyle .d_{1}d_{2}\ldots d_{n}0111\ldots }
2490:
2431:
2404:
2372:
2330:
2306:
2278:
2225:
2205:
2174:
2154:
2093:
2028:
1999:
1973:
1953:
1900:
1880:
1851:
1825:
1799:
1779:
1735:
1711:
1685:
1655:
1597:
1553:
1477:
1457:
1433:
1387:
1347:
1323:
1299:
1271:
1216:
1125:
1038:
1000:
902:
795:
738:
682:
632:
585:
565:
528:
455:
435:
406:
354:
324:
223:
3773:"Nicht konstruktiv beweisbare Sätze der Analysis"
3665:"Representations of reals in reverse mathematics"
3417:
3369:
3357:
1663:. Then there is no Turing machine which on input
4740:
3739:Proceedings of the American Mathematical Society
3033:{\displaystyle \forall (n\in \omega )\phi (x,n)}
796:{\displaystyle \exists rD(r)=\mathrm {false} \;}
3381:
3263:
2685:approximations rather than decimal expansions.
1410:, the set of computable numbers is classically
1395:of machines representing computable reals, and
739:{\displaystyle \exists rD(r)=\mathrm {true} \;}
3875:
3856:Proceedings of the London Mathematical Society
3824:Proceedings of the London Mathematical Society
3641:
3593:"A Survey of Exact Arithmetic Implementations"
3399:
3251:
3160:. The resulting mathematical theory is called
2845:classes or randomness it is easier to work in
224:{\displaystyle f:\mathbb {N} \to \mathbb {Z} }
44:can be computed to arbitrary precision, while
4041:
3967:Stoltenberg-Hansen, V.; Tucker, J.V. (1999).
3947:
3590:
2128:Digit strings and the Cantor and Baire spaces
1719:To see why, suppose the machine described by
1616:The fact that computable real numbers form a
4017:A simple introduction to computable analysis
3336:: CS1 maint: multiple names: authors list (
3115:
2279:{\displaystyle n>\log _{10}(1/\epsilon )}
2120:subset of computable reals without ends) is
2067:any number that encodes the solution of the
1445:provides that there is a minimal element in
1250:
231:in the following manner: given any positive
573:which when provided with a rational number
529:{\displaystyle |q_{i}-q_{i+1}|<2^{-i}\,}
4723:
4048:
4034:
3878:"Computations with effective real numbers"
3702:(1967). "9. The Computable Real Numbers".
2554:denote the same real number, the interval
1529:is nonzero. These operations are actually
1335:(and consequently, neither are subsets of
1213:
1122:
1035:
997:
899:
792:
735:
679:
629:
562:
91:Equivalent definitions can be given using
4524:
4447:
4408:
4370:
4342:
4314:
4286:
4174:
4141:
4113:
4085:
4013:
3989:
3948:Bishop, Errett; Bridges, Douglas (1985).
3929:
3914:"Analysis in the Computable Number Field"
3893:
3750:
3706:Computation: Finite and Infinite Machines
3680:
3537:
3354:(1989), p.8. North-Holland, 0-444-87295-7
3286:
2973:
2914:
2656:approximations for the computable number
2547:{\displaystyle .d_{1}d_{2}\ldots d_{n}10}
2101:, which is a type of real number that is
1403:to demonstrate uncountably many of them.
525:
217:
209:
131:on its initial tape, terminates with the
3642:Bridges, Douglas; Richman, Fred (1987).
3600:Computability and Complexity in Analysis
3527:
2075:) according to a chosen encoding scheme.
1496:
1331:of these Gödel numbers, however, is not
36:
3767:
3435:
3411:
3237:. Rozprawy Matematyczne. Vol. 33.
1627:Computable reals however do not form a
1371:. Consequently, there is no surjective
690:, satisfying the following conditions:
683:{\displaystyle D(r)=\mathrm {false} \;}
407:{\displaystyle |r-a|\leq \varepsilon .}
143:is specified at the start, (2) for any
14:
4741:
3911:
3849:
3821:
3698:
3689:
3578:
3530:Theorem Proving in Higher Order Logics
3375:
3363:
3309:
3101:{\displaystyle x\in \omega ^{\omega }}
2048:, as the first construction is due to
1489:. The inverse of this bijection is an
633:{\displaystyle D(r)=\mathrm {true} \;}
173:whereas the modern definition is not.
4029:
3662:
3645:Varieties of Constructive Mathematics
3591:Gowland, Paul; Lester, David (2001).
3423:
3219:
1954:{\displaystyle \epsilon <|b-a|/2,}
1747:output an approximation which forces
4020:. Fernuniv., Fachbereich Informatik.
4006:§1.3.2 introduces the definition by
3732:
3387:
2290:digits of the decimal expansion for
1375:from the natural numbers to the set
176:
4237:Set-theoretically definable numbers
3168:Implementations of exact arithmetic
2038:
238:, the function produces an integer
24:
4208:
4055:
3904:
2994:
2821:
2088:
1231:corresponding to it. The function
1206:
1203:
1200:
1197:
1194:
1118:
1115:
1112:
1109:
990:
987:
984:
981:
950:
943:
940:
937:
934:
880:
877:
874:
871:
868:
839:
836:
833:
830:
788:
785:
782:
779:
776:
754:
731:
728:
725:
722:
700:
675:
672:
669:
666:
663:
625:
622:
619:
616:
192:if it can be approximated by some
25:
4765:
3752:10.1090/S0002-9939-1954-0063328-5
3690:Lambov, Branimir (5 April 2015).
3439:The American Mathematical Monthly
2980:{\displaystyle x\in \mathbb {R} }
2948:{\displaystyle \omega ^{\omega }}
2895:{\displaystyle \omega ^{\omega }}
1635:Non-computability of the ordering
1406:While the set of real numbers is
1011:An example is given by a program
4722:
3973:Handbook of Computability Theory
3817:from the original on 2018-07-21.
3627:from the original on 2022-03-24.
3517:from the original on 2020-09-24.
2696:perspective, the two structures
2124:to the set of rational numbers.
1961:so by taking increasingly small
3584:
3521:
3466:
3429:
2318:. For the converse, we pick an
4216:{\displaystyle {\mathcal {P}}}
3975:. Elsevier. pp. 363–448.
3876:van der Hoeven, Joris (2006).
3830:(1) (published 1937): 230–65.
3648:. Cambridge University Press.
3344:
3303:
3257:
3213:
3062:
3050:
3027:
3015:
3009:
2997:
2742:
2730:
2573:
2561:
2399:
2387:
2273:
2259:
1936:
1922:
1187:
1173:
1167:
1102:
1088:
1082:
974:
968:
947:
927:
921:
887:
884:
861:
855:
849:
843:
823:
817:
811:
769:
763:
715:
709:
656:
650:
609:
603:
505:
471:
391:
377:
304:
298:
268:
262:
213:
48:real number is not computable.
13:
1:
4571:Plane-based geometric algebra
4008:nested sequences of intervals
3969:"Computable Rings and Fields"
3862:(6) (published 1937): 544–6.
3634:
1245:
68:. They are also known as the
4531:{\displaystyle \mathbb {S} }
4454:{\displaystyle \mathbb {C} }
4415:{\displaystyle \mathbb {R} }
4377:{\displaystyle \mathbb {O} }
4349:{\displaystyle \mathbb {H} }
4321:{\displaystyle \mathbb {C} }
4293:{\displaystyle \mathbb {R} }
4181:{\displaystyle \mathbb {A} }
4148:{\displaystyle \mathbb {Q} }
4120:{\displaystyle \mathbb {Z} }
4092:{\displaystyle \mathbb {N} }
3882:Theoretical Computer Science
3548:10.1007/978-3-540-71067-7_21
3400:Bridges & Richman (1987)
3288:10.1016/0001-8708(83)90004-X
2921:{\displaystyle \mathbb {R} }
2838:{\displaystyle \Pi _{1}^{0}}
355:{\displaystyle \varepsilon }
7:
3733:Rice, Henry Gordon (1954).
3180:
2865:{\displaystyle 2^{\omega }}
2802:{\displaystyle 2^{\omega }}
2775:{\displaystyle 2^{\omega }}
2716:{\displaystyle 2^{\omega }}
2606:{\displaystyle 2^{\omega }}
2432:{\displaystyle 2^{\omega }}
2373:{\displaystyle 2^{\omega }}
2059:Every computable number is
10:
4770:
3971:. In Griffor, E.R. (ed.).
3352:Classical Recursion Theory
3202:Transcomputational problem
3068:{\displaystyle \phi (x,n)}
2186:(The decimal expansion of
2162:as input and produces the
1397:Cantor's diagonal argument
166:string of decimal digits.
29:
4713:
4655:
4581:
4561:Algebra of physical space
4483:
4391:
4262:
4064:
4014:Weihrauch, Klaus (1995).
3990:Weihrauch, Klaus (2000).
3895:10.1016/j.tcs.2005.09.060
3780:Journal of Symbolic Logic
3663:Hirst, Jeffry L. (2007).
3152:(for example, consider a
3116:Use in place of the reals
3110:hyperarithmetic hierarchy
2678:{\displaystyle \epsilon }
2649:{\displaystyle \epsilon }
2629:{\displaystyle \epsilon }
2331:{\displaystyle \epsilon }
2307:{\displaystyle \epsilon }
2226:{\displaystyle \epsilon }
2206:{\displaystyle \epsilon }
1974:{\displaystyle \epsilon }
1901:{\displaystyle \epsilon }
1736:{\displaystyle \epsilon }
1598:{\displaystyle \epsilon }
1554:{\displaystyle \epsilon }
1251:Not computably enumerable
552:is a computable function
135:th digit of that number .
4617:Extended complex numbers
4600:Extended natural numbers
3868:10.1112/plms/s2-43.6.544
3836:10.1112/plms/s2-42.1.230
3735:"Recursive real numbers"
3267:; Richards, Ian (1983).
3207:
2111:Universal Turing machine
2061:arithmetically definable
1888:It is sufficient to use
1712:{\displaystyle a\leq 0.}
1360:, but the corresponding
1039:{\displaystyle q>0\;}
30:Not to be confused with
3912:Aberth, Oliver (1968).
3608:10.1007/3-540-45335-0_3
3274:Advances in Mathematics
3197:Semicomputable function
2690:computability theoretic
2613:not ending in all 1's.
2338:computable real number
2155:{\displaystyle n\geq 1}
2105:to the halting problem.
2094:{\displaystyle \Omega }
2029:{\displaystyle a>b.}
1881:{\displaystyle a>b.}
1826:{\displaystyle a\neq b}
1443:well ordering principle
550:computable Dedekind cut
4673:Transcendental numbers
4532:
4509:Hyperbolic quaternions
4455:
4416:
4378:
4350:
4322:
4294:
4217:
4182:
4149:
4121:
4093:
3850:Turing, A. M. (1938).
3265:Pour-El, Marian Boykan
3158:modulus of convergence
3134:transcendental numbers
3102:
3069:
3034:
2981:
2949:
2922:
2896:
2866:
2839:
2813:, for questions about
2803:
2776:
2749:
2717:
2679:
2650:
2630:
2607:
2580:
2548:
2492:
2433:
2406:
2374:
2332:
2308:
2280:
2227:
2207:
2184:
2176:
2156:
2095:
2030:
2001:
2000:{\displaystyle a<b}
1975:
1955:
1908:-approximations where
1902:
1882:
1853:
1852:{\displaystyle a<b}
1833:, and outputs whether
1827:
1801:
1781:
1767:approximating numbers
1737:
1723:keeps outputting 0 as
1713:
1687:
1686:{\displaystyle a>0}
1657:
1599:
1555:
1479:
1459:
1435:
1389:
1349:
1325:
1301:
1273:
1218:
1127:
1040:
1002:
904:
797:
740:
684:
634:
587:
567:
530:
457:
437:
408:
356:
326:
225:
137:
49:
18:Computable real number
4754:Theory of computation
4605:Extended real numbers
4533:
4456:
4426:Split-complex numbers
4417:
4379:
4351:
4323:
4295:
4218:
4183:
4159:Constructible numbers
4150:
4122:
4094:
3950:Constructive Analysis
3931:10.1145/321450.321460
3490:10.1145/319838.319860
3252:van der Hoeven (2006)
3103:
3070:
3035:
2982:
2950:
2923:
2897:
2867:
2840:
2804:
2777:
2750:
2718:
2680:
2651:
2631:
2608:
2581:
2549:
2493:
2434:
2407:
2375:
2333:
2309:
2281:
2228:
2208:
2177:
2157:
2134:
2096:
2031:
2002:
1976:
1956:
1903:
1883:
1854:
1828:
1802:
1782:
1738:
1714:
1688:
1658:
1600:
1556:
1497:Properties as a field
1480:
1465:which corresponds to
1460:
1436:
1390:
1350:
1333:computably enumerable
1326:
1302:
1274:
1219:
1128:
1041:
1003:
905:
798:
741:
685:
635:
588:
568:
531:
458:
438:
436:{\displaystyle q_{i}}
409:
357:
327:
226:
171:table-maker's dilemma
125:
93:μ-recursive functions
40:
4749:Computability theory
4637:Supernatural numbers
4547:Multicomplex numbers
4520:
4504:Dual-complex numbers
4443:
4404:
4366:
4338:
4310:
4282:
4264:Composition algebras
4232:Arithmetical numbers
4203:
4170:
4137:
4109:
4081:
3484:. pp. 162–173.
3225:Grzegorczyk, Andrzej
3187:Constructible number
3079:
3044:
2991:
2963:
2932:
2910:
2879:
2849:
2817:
2811:totally disconnected
2786:
2759:
2727:
2700:
2669:
2640:
2620:
2590:
2558:
2502:
2443:
2416:
2384:
2357:
2322:
2298:
2237:
2217:
2197:
2166:
2140:
2085:
2011:
1985:
1965:
1912:
1892:
1863:
1837:
1811:
1791:
1771:
1727:
1697:
1671:
1647:
1620:was first proved by
1589:
1545:
1531:uniformly computable
1469:
1449:
1422:
1379:
1339:
1315:
1291:
1263:
1138:
1053:
1046:this is defined by:
1023:
915:
808:
751:
697:
644:
597:
577:
556:
467:
447:
420:
373:
346:
253:
199:
32:constructible number
4542:Split-biquaternions
4254:Eisenstein integers
4192:Closed-form numbers
3992:Computable analysis
3234:Computable analysis
3162:computable analysis
2834:
2073:undecidable problem
2054:computable analysis
1373:computable function
566:{\displaystyle D\;}
194:computable function
4700:Profinite integers
4663:Irrational numbers
4528:
4451:
4412:
4374:
4346:
4318:
4290:
4247:Gaussian rationals
4227:Computable numbers
4213:
4178:
4145:
4117:
4089:
3098:
3065:
3030:
2977:
2945:
2918:
2892:
2862:
2835:
2820:
2799:
2772:
2745:
2713:
2675:
2646:
2626:
2603:
2576:
2544:
2488:
2429:
2402:
2370:
2328:
2304:
2276:
2223:
2203:
2172:
2152:
2091:
2079:Chaitin's constant
2026:
1997:
1971:
1951:
1898:
1878:
1849:
1823:
1797:
1777:
1733:
1709:
1683:
1653:
1595:
1561:) produces output
1551:
1475:
1455:
1434:{\displaystyle x,}
1431:
1385:
1345:
1321:
1297:
1269:
1214:
1123:
1036:
998:
900:
793:
736:
680:
630:
583:
563:
526:
453:
433:
404:
352:
322:
221:
115:In the following,
58:computable numbers
50:
4736:
4735:
4647:Superreal numbers
4627:Levi-Civita field
4622:Hyperreal numbers
4566:Spacetime algebra
4552:Geometric algebra
4465:Bicomplex numbers
4431:Split-quaternions
4272:Division algebras
4242:Gaussian integers
4164:Algebraic numbers
4067:definable numbers
3982:978-0-08-053304-9
3710:. Prentice-Hall.
3655:978-0-521-31802-0
3617:978-3-540-42197-9
3557:978-3-540-71065-3
3132:, and many other
3122:algebraic numbers
2694:measure theoretic
2412:. The members of
2314:approximation of
2286:, then the first
2175:{\displaystyle n}
2103:Turing equivalent
1800:{\displaystyle b}
1780:{\displaystyle a}
1667:outputs "YES" if
1656:{\displaystyle a}
1622:Henry Gordon Rice
1605:approximation of
1478:{\displaystyle x}
1458:{\displaystyle S}
1388:{\displaystyle S}
1348:{\displaystyle S}
1324:{\displaystyle S}
1300:{\displaystyle S}
1272:{\displaystyle S}
1015:that defines the
593:as input returns
586:{\displaystyle r}
456:{\displaystyle a}
317:
281:
177:Formal definition
105:real closed field
74:effective numbers
70:recursive numbers
16:(Redirected from
4761:
4726:
4725:
4693:
4683:
4595:Cardinal numbers
4556:Clifford algebra
4537:
4535:
4534:
4529:
4527:
4499:Dual quaternions
4460:
4458:
4457:
4452:
4450:
4421:
4419:
4418:
4413:
4411:
4383:
4381:
4380:
4375:
4373:
4355:
4353:
4352:
4347:
4345:
4327:
4325:
4324:
4319:
4317:
4299:
4297:
4296:
4291:
4289:
4222:
4220:
4219:
4214:
4212:
4211:
4187:
4185:
4184:
4179:
4177:
4154:
4152:
4151:
4146:
4144:
4131:Rational numbers
4126:
4124:
4123:
4118:
4116:
4098:
4096:
4095:
4090:
4088:
4050:
4043:
4036:
4027:
4026:
4021:
4005:
3986:
3963:
3943:
3933:
3899:
3897:
3871:
3847:
3818:
3816:
3777:
3764:
3754:
3729:
3709:
3695:
3686:
3684:
3682:10.4064/ba55-4-2
3659:
3629:
3628:
3626:
3597:
3588:
3582:
3576:
3570:
3569:
3541:
3525:
3519:
3518:
3516:
3479:
3470:
3464:
3463:
3452:10.2307/27641983
3433:
3427:
3421:
3415:
3409:
3403:
3397:
3391:
3385:
3379:
3373:
3367:
3361:
3355:
3348:
3342:
3341:
3335:
3327:
3307:
3301:
3300:
3290:
3261:
3255:
3249:
3243:
3242:
3221:Mazur, Stanisław
3217:
3192:Definable number
3154:Specker sequence
3150:bounded sequence
3107:
3105:
3104:
3099:
3097:
3096:
3074:
3072:
3071:
3066:
3039:
3037:
3036:
3031:
2986:
2984:
2983:
2978:
2976:
2954:
2952:
2951:
2946:
2944:
2943:
2927:
2925:
2924:
2919:
2917:
2901:
2899:
2898:
2893:
2891:
2890:
2871:
2869:
2868:
2863:
2861:
2860:
2844:
2842:
2841:
2836:
2833:
2828:
2808:
2806:
2805:
2800:
2798:
2797:
2782:as reals. While
2781:
2779:
2778:
2773:
2771:
2770:
2754:
2752:
2751:
2748:{\displaystyle }
2746:
2722:
2720:
2719:
2714:
2712:
2711:
2688:However, from a
2684:
2682:
2681:
2676:
2655:
2653:
2652:
2647:
2635:
2633:
2632:
2627:
2612:
2610:
2609:
2604:
2602:
2601:
2585:
2583:
2582:
2579:{\displaystyle }
2577:
2553:
2551:
2550:
2545:
2540:
2539:
2527:
2526:
2517:
2516:
2497:
2495:
2494:
2489:
2481:
2480:
2468:
2467:
2458:
2457:
2438:
2436:
2435:
2430:
2428:
2427:
2411:
2409:
2408:
2405:{\displaystyle }
2403:
2379:
2377:
2376:
2371:
2369:
2368:
2337:
2335:
2334:
2329:
2313:
2311:
2310:
2305:
2285:
2283:
2282:
2277:
2269:
2255:
2254:
2232:
2230:
2229:
2224:
2212:
2210:
2209:
2204:
2181:
2179:
2178:
2173:
2161:
2159:
2158:
2153:
2122:order-isomorphic
2100:
2098:
2097:
2092:
2046:Specker sequence
2039:Other properties
2035:
2033:
2032:
2027:
2006:
2004:
2003:
1998:
1980:
1978:
1977:
1972:
1960:
1958:
1957:
1952:
1944:
1939:
1925:
1907:
1905:
1904:
1899:
1887:
1885:
1884:
1879:
1858:
1856:
1855:
1850:
1832:
1830:
1829:
1824:
1806:
1804:
1803:
1798:
1786:
1784:
1783:
1778:
1742:
1740:
1739:
1734:
1718:
1716:
1715:
1710:
1692:
1690:
1689:
1684:
1662:
1660:
1659:
1654:
1629:computable field
1604:
1602:
1601:
1596:
1560:
1558:
1557:
1552:
1484:
1482:
1481:
1476:
1464:
1462:
1461:
1456:
1440:
1438:
1437:
1432:
1394:
1392:
1391:
1386:
1362:decision problem
1354:
1352:
1351:
1346:
1330:
1328:
1327:
1322:
1306:
1304:
1303:
1298:
1278:
1276:
1275:
1270:
1223:
1221:
1220:
1215:
1209:
1183:
1166:
1165:
1150:
1149:
1132:
1130:
1129:
1124:
1121:
1098:
1081:
1080:
1065:
1064:
1045:
1043:
1042:
1037:
1007:
1005:
1004:
999:
993:
946:
909:
907:
906:
901:
883:
842:
802:
800:
799:
794:
791:
745:
743:
742:
737:
734:
689:
687:
686:
681:
678:
639:
637:
636:
631:
628:
592:
590:
589:
584:
572:
570:
569:
564:
535:
533:
532:
527:
524:
523:
508:
503:
502:
484:
483:
474:
462:
460:
459:
454:
442:
440:
439:
434:
432:
431:
413:
411:
410:
405:
394:
380:
361:
359:
358:
353:
331:
329:
328:
323:
318:
313:
293:
282:
277:
257:
230:
228:
227:
222:
220:
212:
78:computable reals
21:
4769:
4768:
4764:
4763:
4762:
4760:
4759:
4758:
4739:
4738:
4737:
4732:
4709:
4688:
4678:
4651:
4642:Surreal numbers
4632:Ordinal numbers
4577:
4523:
4521:
4518:
4517:
4479:
4446:
4444:
4441:
4440:
4438:
4436:Split-octonions
4407:
4405:
4402:
4401:
4393:
4387:
4369:
4367:
4364:
4363:
4341:
4339:
4336:
4335:
4313:
4311:
4308:
4307:
4304:Complex numbers
4285:
4283:
4280:
4279:
4258:
4207:
4206:
4204:
4201:
4200:
4173:
4171:
4168:
4167:
4140:
4138:
4135:
4134:
4112:
4110:
4107:
4106:
4084:
4082:
4079:
4078:
4075:Natural numbers
4060:
4054:
4024:
4002:
3983:
3960:
3907:
3905:Further reading
3902:
3848:
3814:
3792:10.2307/2267043
3775:
3718:
3656:
3637:
3632:
3624:
3618:
3595:
3589:
3585:
3577:
3573:
3558:
3526:
3522:
3514:
3500:
3477:
3471:
3467:
3434:
3430:
3422:
3418:
3410:
3406:
3398:
3394:
3386:
3382:
3374:
3370:
3362:
3358:
3349:
3345:
3329:
3328:
3308:
3304:
3262:
3258:
3250:
3246:
3229:Rasiowa, Helena
3218:
3214:
3210:
3183:
3170:
3118:
3092:
3088:
3080:
3077:
3076:
3045:
3042:
3041:
2992:
2989:
2988:
2972:
2964:
2961:
2960:
2957:locally compact
2939:
2935:
2933:
2930:
2929:
2913:
2911:
2908:
2907:
2886:
2882:
2880:
2877:
2876:
2856:
2852:
2850:
2847:
2846:
2829:
2824:
2818:
2815:
2814:
2793:
2789:
2787:
2784:
2783:
2766:
2762:
2760:
2757:
2756:
2728:
2725:
2724:
2707:
2703:
2701:
2698:
2697:
2670:
2667:
2666:
2641:
2638:
2637:
2621:
2618:
2617:
2597:
2593:
2591:
2588:
2587:
2559:
2556:
2555:
2535:
2531:
2522:
2518:
2512:
2508:
2503:
2500:
2499:
2476:
2472:
2463:
2459:
2453:
2449:
2444:
2441:
2440:
2423:
2419:
2417:
2414:
2413:
2385:
2382:
2381:
2364:
2360:
2358:
2355:
2354:
2323:
2320:
2319:
2299:
2296:
2295:
2265:
2250:
2246:
2238:
2235:
2234:
2218:
2215:
2214:
2198:
2195:
2194:
2167:
2164:
2163:
2141:
2138:
2137:
2130:
2118:densely ordered
2086:
2083:
2082:
2069:halting problem
2041:
2012:
2009:
2008:
1986:
1983:
1982:
1966:
1963:
1962:
1940:
1935:
1921:
1913:
1910:
1909:
1893:
1890:
1889:
1864:
1861:
1860:
1838:
1835:
1834:
1812:
1809:
1808:
1792:
1789:
1788:
1772:
1769:
1768:
1728:
1725:
1724:
1698:
1695:
1694:
1672:
1669:
1668:
1648:
1645:
1644:
1637:
1590:
1587:
1586:
1546:
1543:
1542:
1499:
1470:
1467:
1466:
1450:
1447:
1446:
1423:
1420:
1419:
1399:cannot be used
1380:
1377:
1376:
1369:0′′
1340:
1337:
1336:
1316:
1313:
1312:
1292:
1289:
1288:
1281:natural numbers
1264:
1261:
1260:
1253:
1248:
1193:
1179:
1161:
1157:
1145:
1141:
1139:
1136:
1135:
1108:
1094:
1076:
1072:
1060:
1056:
1054:
1051:
1050:
1024:
1021:
1020:
1019:of 3. Assuming
980:
933:
916:
913:
912:
867:
829:
809:
806:
805:
775:
752:
749:
748:
721:
698:
695:
694:
662:
645:
642:
641:
615:
598:
595:
594:
578:
575:
574:
557:
554:
553:
516:
512:
504:
492:
488:
479:
475:
470:
468:
465:
464:
448:
445:
444:
427:
423:
421:
418:
417:
390:
376:
374:
371:
370:
364:rational number
347:
344:
343:
294:
292:
258:
256:
254:
251:
250:
216:
208:
200:
197:
196:
179:
113:
97:Turing machines
82:recursive reals
35:
28:
23:
22:
15:
12:
11:
5:
4767:
4757:
4756:
4751:
4734:
4733:
4731:
4730:
4720:
4718:Classification
4714:
4711:
4710:
4708:
4707:
4705:Normal numbers
4702:
4697:
4675:
4670:
4665:
4659:
4657:
4653:
4652:
4650:
4649:
4644:
4639:
4634:
4629:
4624:
4619:
4614:
4613:
4612:
4602:
4597:
4591:
4589:
4587:infinitesimals
4579:
4578:
4576:
4575:
4574:
4573:
4568:
4563:
4549:
4544:
4539:
4526:
4511:
4506:
4501:
4496:
4490:
4488:
4481:
4480:
4478:
4477:
4472:
4467:
4462:
4449:
4433:
4428:
4423:
4410:
4397:
4395:
4389:
4388:
4386:
4385:
4372:
4357:
4344:
4329:
4316:
4301:
4288:
4268:
4266:
4260:
4259:
4257:
4256:
4251:
4250:
4249:
4239:
4234:
4229:
4224:
4210:
4194:
4189:
4176:
4161:
4156:
4143:
4128:
4115:
4100:
4087:
4071:
4069:
4062:
4061:
4053:
4052:
4045:
4038:
4030:
4023:
4022:
4011:
4000:
3987:
3981:
3964:
3958:
3945:
3924:(2): 276–299.
3908:
3906:
3903:
3901:
3900:
3873:
3819:
3786:(3): 145–158.
3765:
3745:(5): 784–791.
3730:
3716:
3700:Minsky, Marvin
3696:
3687:
3675:(4): 303–316.
3660:
3654:
3638:
3636:
3633:
3631:
3630:
3616:
3583:
3571:
3556:
3520:
3498:
3465:
3446:(6): 559–566.
3428:
3416:
3412:Specker (1949)
3404:
3392:
3380:
3368:
3356:
3350:P. Odifreddi,
3343:
3302:
3256:
3244:
3211:
3209:
3206:
3205:
3204:
3199:
3194:
3189:
3182:
3179:
3169:
3166:
3138:constructivist
3117:
3114:
3095:
3091:
3087:
3084:
3064:
3061:
3058:
3055:
3052:
3049:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2975:
2971:
2968:
2942:
2938:
2916:
2889:
2885:
2859:
2855:
2832:
2827:
2823:
2796:
2792:
2769:
2765:
2744:
2741:
2738:
2735:
2732:
2710:
2706:
2674:
2645:
2625:
2600:
2596:
2575:
2572:
2569:
2566:
2563:
2543:
2538:
2534:
2530:
2525:
2521:
2515:
2511:
2507:
2487:
2484:
2479:
2475:
2471:
2466:
2462:
2456:
2452:
2448:
2426:
2422:
2401:
2398:
2395:
2392:
2389:
2367:
2363:
2327:
2303:
2275:
2272:
2268:
2264:
2261:
2258:
2253:
2249:
2245:
2242:
2222:
2202:
2171:
2151:
2148:
2145:
2129:
2126:
2107:
2106:
2090:
2076:
2071:(or any other
2040:
2037:
2025:
2022:
2019:
2016:
1996:
1993:
1990:
1970:
1950:
1947:
1943:
1938:
1934:
1931:
1928:
1924:
1920:
1917:
1897:
1877:
1874:
1871:
1868:
1848:
1845:
1842:
1822:
1819:
1816:
1796:
1776:
1732:
1708:
1705:
1702:
1682:
1679:
1676:
1652:
1636:
1633:
1594:
1550:
1498:
1495:
1474:
1454:
1430:
1427:
1401:constructively
1384:
1358:total function
1344:
1320:
1296:
1268:
1252:
1249:
1247:
1244:
1240:complex number
1225:
1224:
1212:
1208:
1205:
1202:
1199:
1196:
1192:
1189:
1186:
1182:
1178:
1175:
1172:
1169:
1164:
1160:
1156:
1153:
1148:
1144:
1133:
1120:
1117:
1114:
1111:
1107:
1104:
1101:
1097:
1093:
1090:
1087:
1084:
1079:
1075:
1071:
1068:
1063:
1059:
1034:
1031:
1028:
1009:
1008:
996:
992:
989:
986:
983:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
945:
942:
939:
936:
932:
929:
926:
923:
920:
910:
898:
895:
892:
889:
886:
882:
879:
876:
873:
870:
866:
863:
860:
857:
854:
851:
848:
845:
841:
838:
835:
832:
828:
825:
822:
819:
816:
813:
803:
790:
787:
784:
781:
778:
774:
771:
768:
765:
762:
759:
756:
746:
733:
730:
727:
724:
720:
717:
714:
711:
708:
705:
702:
677:
674:
671:
668:
665:
661:
658:
655:
652:
649:
627:
624:
621:
618:
614:
611:
608:
605:
602:
582:
561:
542:
541:
522:
519:
515:
511:
507:
501:
498:
495:
491:
487:
482:
478:
473:
452:
443:converging to
430:
426:
414:
403:
400:
397:
393:
389:
386:
383:
379:
351:
333:
332:
321:
316:
312:
309:
306:
303:
300:
297:
291:
288:
285:
280:
276:
273:
270:
267:
264:
261:
219:
215:
211:
207:
204:
178:
175:
112:
109:
26:
9:
6:
4:
3:
2:
4766:
4755:
4752:
4750:
4747:
4746:
4744:
4729:
4721:
4719:
4716:
4715:
4712:
4706:
4703:
4701:
4698:
4695:
4691:
4685:
4681:
4676:
4674:
4671:
4669:
4668:Fuzzy numbers
4666:
4664:
4661:
4660:
4658:
4654:
4648:
4645:
4643:
4640:
4638:
4635:
4633:
4630:
4628:
4625:
4623:
4620:
4618:
4615:
4611:
4608:
4607:
4606:
4603:
4601:
4598:
4596:
4593:
4592:
4590:
4588:
4584:
4580:
4572:
4569:
4567:
4564:
4562:
4559:
4558:
4557:
4553:
4550:
4548:
4545:
4543:
4540:
4515:
4512:
4510:
4507:
4505:
4502:
4500:
4497:
4495:
4492:
4491:
4489:
4487:
4482:
4476:
4473:
4471:
4470:Biquaternions
4468:
4466:
4463:
4437:
4434:
4432:
4429:
4427:
4424:
4399:
4398:
4396:
4390:
4361:
4358:
4333:
4330:
4305:
4302:
4277:
4273:
4270:
4269:
4267:
4265:
4261:
4255:
4252:
4248:
4245:
4244:
4243:
4240:
4238:
4235:
4233:
4230:
4228:
4225:
4198:
4195:
4193:
4190:
4165:
4162:
4160:
4157:
4132:
4129:
4104:
4101:
4076:
4073:
4072:
4070:
4068:
4063:
4058:
4051:
4046:
4044:
4039:
4037:
4032:
4031:
4028:
4019:
4018:
4012:
4009:
4003:
4001:3-540-66817-9
3997:
3993:
3988:
3984:
3978:
3974:
3970:
3965:
3961:
3959:0-387-15066-8
3955:
3951:
3946:
3941:
3937:
3932:
3927:
3923:
3919:
3915:
3910:
3909:
3896:
3891:
3887:
3883:
3879:
3874:
3869:
3865:
3861:
3857:
3853:
3845:
3841:
3837:
3833:
3829:
3825:
3820:
3813:
3809:
3805:
3801:
3797:
3793:
3789:
3785:
3781:
3774:
3770:
3766:
3762:
3758:
3753:
3748:
3744:
3740:
3736:
3731:
3727:
3723:
3719:
3717:0-13-165563-9
3713:
3708:
3707:
3701:
3697:
3693:
3688:
3683:
3678:
3674:
3670:
3666:
3661:
3657:
3651:
3647:
3646:
3640:
3639:
3623:
3619:
3613:
3609:
3605:
3601:
3594:
3587:
3580:
3579:Lambov (2015)
3575:
3567:
3563:
3559:
3553:
3549:
3545:
3540:
3535:
3531:
3524:
3513:
3509:
3505:
3501:
3495:
3491:
3487:
3483:
3476:
3469:
3461:
3457:
3453:
3449:
3445:
3441:
3440:
3432:
3425:
3420:
3413:
3408:
3402:, p. 58.
3401:
3396:
3389:
3384:
3377:
3376:Minsky (1967)
3372:
3365:
3364:Turing (1936)
3360:
3353:
3347:
3339:
3333:
3325:
3321:
3317:
3313:
3306:
3298:
3294:
3289:
3284:
3280:
3276:
3275:
3270:
3266:
3260:
3253:
3248:
3240:
3236:
3235:
3230:
3226:
3222:
3216:
3212:
3203:
3200:
3198:
3195:
3193:
3190:
3188:
3185:
3184:
3178:
3176:
3165:
3163:
3159:
3155:
3151:
3147:
3141:
3139:
3135:
3131:
3127:
3124:, as well as
3123:
3113:
3111:
3093:
3089:
3085:
3082:
3059:
3056:
3053:
3047:
3024:
3021:
3018:
3012:
3006:
3003:
3000:
2969:
2966:
2958:
2940:
2936:
2905:
2887:
2883:
2873:
2857:
2853:
2830:
2825:
2812:
2794:
2790:
2767:
2763:
2739:
2736:
2733:
2708:
2704:
2695:
2691:
2686:
2672:
2663:
2659:
2643:
2623:
2614:
2598:
2594:
2570:
2567:
2564:
2541:
2536:
2532:
2528:
2523:
2519:
2513:
2509:
2505:
2485:
2482:
2477:
2473:
2469:
2464:
2460:
2454:
2450:
2446:
2424:
2420:
2396:
2393:
2390:
2365:
2361:
2351:
2349:
2345:
2341:
2325:
2317:
2301:
2293:
2289:
2270:
2266:
2262:
2256:
2251:
2247:
2243:
2240:
2220:
2200:
2191:
2189:
2183:
2169:
2149:
2146:
2143:
2133:
2125:
2123:
2119:
2114:
2112:
2104:
2080:
2077:
2074:
2070:
2066:
2065:
2064:
2062:
2057:
2055:
2051:
2050:Ernst Specker
2047:
2036:
2023:
2020:
2017:
2014:
1994:
1991:
1988:
1968:
1948:
1945:
1941:
1932:
1929:
1926:
1918:
1915:
1895:
1875:
1872:
1869:
1866:
1846:
1843:
1840:
1820:
1817:
1814:
1794:
1774:
1766:
1762:
1757:
1755:
1754:Dedekind cuts
1750:
1746:
1730:
1722:
1706:
1703:
1700:
1680:
1677:
1674:
1666:
1650:
1642:
1632:
1630:
1625:
1623:
1619:
1614:
1612:
1608:
1592:
1584:
1580:
1576:
1572:
1568:
1564:
1548:
1540:
1536:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1494:
1492:
1488:
1472:
1452:
1444:
1428:
1425:
1417:
1413:
1409:
1404:
1402:
1398:
1382:
1374:
1370:
1367:
1366:Turing degree
1363:
1359:
1342:
1334:
1318:
1310:
1294:
1286:
1282:
1266:
1258:
1243:
1241:
1236:
1234:
1230:
1210:
1190:
1184:
1180:
1176:
1170:
1162:
1158:
1154:
1151:
1146:
1142:
1134:
1105:
1099:
1095:
1091:
1085:
1077:
1073:
1069:
1066:
1061:
1057:
1049:
1048:
1047:
1032:
1029:
1026:
1018:
1014:
994:
977:
971:
965:
962:
959:
956:
953:
930:
924:
918:
911:
896:
893:
890:
864:
858:
852:
846:
826:
820:
814:
804:
772:
766:
760:
757:
747:
718:
712:
706:
703:
693:
692:
691:
659:
653:
647:
612:
606:
600:
580:
559:
551:
547:
546:Dedekind cuts
539:
520:
517:
513:
509:
499:
496:
493:
489:
485:
480:
476:
450:
428:
424:
415:
401:
398:
395:
387:
384:
381:
368:
365:
362:, produces a
349:
342:
338:
337:
336:
319:
314:
310:
307:
301:
295:
289:
286:
283:
278:
274:
271:
265:
259:
249:
248:
247:
246:) such that:
245:
241:
237:
234:
205:
202:
195:
191:
187:
184:
174:
172:
167:
165:
161:
157:
153:
148:
146:
142:
136:
134:
130:
124:
122:
118:
117:Marvin Minsky
108:
106:
102:
98:
94:
89:
87:
83:
79:
75:
71:
67:
63:
59:
55:
47:
43:
39:
33:
19:
4689:
4679:
4494:Dual numbers
4486:hypercomplex
4276:Real numbers
4226:
4016:
3991:
3972:
3952:. Springer.
3949:
3921:
3917:
3888:(1): 52–60.
3885:
3881:
3859:
3858:. Series 2.
3855:
3827:
3826:. Series 2.
3823:
3783:
3779:
3742:
3738:
3705:
3672:
3668:
3644:
3599:
3586:
3574:
3529:
3523:
3481:
3468:
3443:
3437:
3431:
3424:Hirst (2007)
3419:
3407:
3395:
3383:
3371:
3359:
3351:
3346:
3332:cite journal
3315:
3311:
3305:
3281:(1): 44–74.
3278:
3272:
3259:
3247:
3241:. p. 4.
3233:
3215:
3171:
3142:
3129:
3125:
3119:
2904:homeomorphic
2875:Elements of
2874:
2687:
2661:
2657:
2615:
2352:
2347:
2343:
2339:
2315:
2291:
2287:
2192:
2187:
2185:
2135:
2131:
2115:
2108:
2058:
2042:
1764:
1760:
1758:
1748:
1744:
1720:
1693:and "NO" if
1664:
1640:
1638:
1626:
1615:
1610:
1606:
1582:
1578:
1574:
1570:
1566:
1562:
1538:
1534:
1530:
1526:
1522:
1518:
1514:
1510:
1506:
1502:
1500:
1405:
1368:
1309:subcountable
1257:Gödel number
1255:Assigning a
1254:
1237:
1232:
1228:
1226:
1012:
1010:
549:
543:
537:
366:
334:
243:
239:
235:
189:
185:
180:
168:
163:
159:
155:
151:
149:
144:
140:
138:
132:
128:
126:
114:
90:
81:
77:
73:
69:
62:real numbers
57:
51:
46:almost every
4656:Other types
4475:Bioctonions
4332:Quaternions
3769:Specker, E.
3388:Rice (1954)
3318:: 114–130.
2987:satisfying
2955:isn't even
2294:provide an
1408:uncountable
341:error bound
183:real number
121:Alan Turing
86:Émile Borel
54:mathematics
4743:Categories
4610:Projective
4583:Infinities
3726:0131655639
3635:References
3499:0897912004
2233:sense: if
1416:almost all
1311:. The set
1285:surjection
1246:Properties
463:such that
369:such that
190:computable
101:λ-calculus
4694:solenoids
4514:Sedenions
4360:Octonions
3694:. GitHub.
3692:"RealLib"
3539:0805.2438
3094:ω
3090:ω
3086:∈
3048:ϕ
3013:ϕ
3007:ω
3004:∈
2995:∀
2970:∈
2941:ω
2937:ω
2906:image of
2888:ω
2884:ω
2858:ω
2822:Π
2795:ω
2768:ω
2709:ω
2673:ϵ
2644:ϵ
2624:ϵ
2599:ω
2529:…
2486:…
2470:…
2425:ω
2366:ω
2326:ϵ
2302:ϵ
2271:ϵ
2257:
2221:ϵ
2201:ϵ
2147:≥
2089:Ω
1969:ϵ
1930:−
1916:ϵ
1896:ϵ
1818:≠
1731:ϵ
1704:≤
1624:in 1954.
1593:ϵ
1549:ϵ
1491:injection
1487:bijection
1414:and thus
1412:countable
1168:⇒
1083:⇒
1017:cube root
951:∃
948:⇒
888:⇒
847:∧
755:∃
701:∃
536:for each
518:−
486:−
399:ε
396:≤
385:−
350:ε
290:≤
284:≤
272:−
214:→
66:algorithm
4103:Integers
4065:Sets of
3940:18135005
3812:Archived
3808:11382421
3771:(1949).
3622:Archived
3566:17959745
3512:Archived
3508:12934546
3231:(eds.).
3223:(1963).
3181:See also
3175:real RAM
3146:supremum
1807:, where
1565:, where
164:infinite
60:are the
4684:numbers
4516: (
4362: (
4334: (
4306: (
4278: (
4199: (
4197:Periods
4166: (
4133: (
4105: (
4077: (
4059:systems
3800:2267043
3761:2031867
3460:2231143
3324:0099923
3297:0697614
3040:, with
1279:of the
233:integer
76:or the
4484:Other
4057:Number
3998:
3979:
3956:
3938:
3842:
3806:
3798:
3759:
3724:
3714:
3652:
3614:
3564:
3554:
3506:
3496:
3458:
3322:
3295:
1585:is an
1581:, and
1521:, and
1364:is in
160:finite
4692:-adic
4682:-adic
4439:Over
4400:Over
4394:types
4392:Split
3936:S2CID
3844:73712
3840:S2CID
3815:(PDF)
3804:S2CID
3796:JSTOR
3776:(PDF)
3757:JSTOR
3625:(PDF)
3596:(PDF)
3562:S2CID
3534:arXiv
3515:(PDF)
3504:S2CID
3478:(PDF)
3208:Notes
3148:of a
1745:never
1618:field
1515:a - b
1511:a + b
1287:from
99:, or
4728:List
4585:and
3996:ISBN
3977:ISBN
3954:ISBN
3722:OCLC
3712:ISBN
3650:ISBN
3612:ISBN
3552:ISBN
3494:ISBN
3338:link
2723:and
2498:and
2483:0111
2244:>
2018:>
1992:<
1919:<
1870:>
1844:<
1787:and
1763:and
1678:>
1505:and
1441:the
1152:>
1067:<
1030:>
957:>
894:<
548:. A
510:<
3926:doi
3890:doi
3886:351
3864:doi
3832:doi
3788:doi
3747:doi
3677:doi
3604:doi
3544:doi
3486:doi
3448:doi
3444:113
3283:doi
2809:is
2692:or
2248:log
2007:or
1859:or
1525:if
1523:a/b
640:or
188:is
80:or
52:In
4745::
4274::
3934:.
3922:15
3920:.
3916:.
3884:.
3880:.
3860:43
3854:.
3838:.
3828:42
3810:.
3802:.
3794:.
3784:14
3782:.
3778:.
3755:.
3741:.
3737:.
3720:.
3673:55
3671:.
3667:.
3620:.
3610:.
3598:.
3560:.
3550:.
3542:.
3510:.
3502:.
3492:.
3480:.
3456:MR
3454:.
3442:.
3334:}}
3330:{{
3320:MR
3314:.
3293:MR
3291:.
3279:48
3277:.
3271:.
3227:;
3164:.
3128:,
3112:.
2928:,
2872:.
2542:10
2252:10
2081:,
2056:.
1707:0.
1613:.
1573:,
1519:ab
1517:,
1513:,
1238:A
181:A
95:,
72:,
56:,
4696:)
4690:p
4686:(
4680:p
4554:/
4538:)
4525:S
4461::
4448:C
4422::
4409:R
4384:)
4371:O
4356:)
4343:H
4328:)
4315:C
4300:)
4287:R
4223:)
4209:P
4188:)
4175:A
4155:)
4142:Q
4127:)
4114:Z
4099:)
4086:N
4049:e
4042:t
4035:v
4004:.
3985:.
3962:.
3942:.
3928::
3898:.
3892::
3870:.
3866::
3846:.
3834::
3790::
3763:.
3749::
3743:5
3728:.
3685:.
3679::
3658:.
3606::
3581:.
3568:.
3546::
3536::
3488::
3462:.
3450::
3426:.
3414:.
3390:.
3378:.
3366:.
3340:)
3326:.
3316:7
3299:.
3285::
3254:.
3130:π
3126:e
3083:x
3063:)
3060:n
3057:,
3054:x
3051:(
3028:)
3025:n
3022:,
3019:x
3016:(
3010:)
3001:n
2998:(
2974:R
2967:x
2915:R
2854:2
2831:0
2826:1
2791:2
2764:2
2743:]
2740:1
2737:,
2734:0
2731:[
2705:2
2662:a
2658:a
2595:2
2574:]
2571:1
2568:,
2565:0
2562:[
2537:n
2533:d
2524:2
2520:d
2514:1
2510:d
2506:.
2478:n
2474:d
2465:2
2461:d
2455:1
2451:d
2447:.
2421:2
2400:]
2397:1
2394:,
2391:0
2388:[
2362:2
2348:a
2344:n
2340:a
2316:a
2292:a
2288:n
2274:)
2267:/
2263:1
2260:(
2241:n
2188:a
2170:n
2150:1
2144:n
2024:.
2021:b
2015:a
1995:b
1989:a
1949:,
1946:2
1942:/
1937:|
1933:a
1927:b
1923:|
1876:.
1873:b
1867:a
1847:b
1841:a
1821:b
1815:a
1795:b
1775:a
1765:B
1761:A
1749:a
1721:A
1701:a
1681:0
1675:a
1665:A
1651:a
1641:A
1611:b
1609:+
1607:a
1583:r
1579:b
1575:B
1571:a
1567:A
1563:r
1541:,
1539:B
1537:,
1535:A
1527:b
1507:b
1503:a
1473:x
1453:S
1429:,
1426:x
1383:S
1343:S
1319:S
1295:S
1267:S
1233:D
1229:D
1211:.
1207:e
1204:s
1201:l
1198:a
1195:f
1191:=
1188:)
1185:q
1181:/
1177:p
1174:(
1171:D
1163:3
1159:q
1155:3
1147:3
1143:p
1119:e
1116:u
1113:r
1110:t
1106:=
1103:)
1100:q
1096:/
1092:p
1089:(
1086:D
1078:3
1074:q
1070:3
1062:3
1058:p
1033:0
1027:q
1013:D
995:.
991:e
988:u
985:r
982:t
978:=
975:)
972:s
969:(
966:D
963:,
960:r
954:s
944:e
941:u
938:r
935:t
931:=
928:)
925:r
922:(
919:D
897:s
891:r
885:)
881:e
878:s
875:l
872:a
869:f
865:=
862:)
859:s
856:(
853:D
850:(
844:)
840:e
837:u
834:r
831:t
827:=
824:)
821:r
818:(
815:D
812:(
789:e
786:s
783:l
780:a
777:f
773:=
770:)
767:r
764:(
761:D
758:r
732:e
729:u
726:r
723:t
719:=
716:)
713:r
710:(
707:D
704:r
676:e
673:s
670:l
667:a
664:f
660:=
657:)
654:r
651:(
648:D
626:e
623:u
620:r
617:t
613:=
610:)
607:r
604:(
601:D
581:r
560:D
540:.
538:i
521:i
514:2
506:|
500:1
497:+
494:i
490:q
481:i
477:q
472:|
451:a
429:i
425:q
402:.
392:|
388:a
382:r
378:|
367:r
320:.
315:n
311:1
308:+
305:)
302:n
299:(
296:f
287:a
279:n
275:1
269:)
266:n
263:(
260:f
244:n
242:(
240:f
236:n
218:Z
210:N
206::
203:f
186:a
156:n
152:n
145:n
141:n
133:n
129:n
42:π
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.