On Unprecise Numbers

www.ramoncasares.com 20251020 Numbers 1 On Unprecise Numbers Ramo´n Casares orcid: 0000-0003-4973-3128 Regarding computability, there are three kinds of real numbers: the computable, the random, and the unprecise numbers. Some unprecise numbers are those based on Rado´’s busy beaver functions, Chaitin’s constant Ω, Turing’s uncomputable number δ, and those coding the halting problem oracle of a Turing complete language. All these unprecise numbers are complete, because they can only be defined in a Turing complete language, but we prove, against one of Turing’s intuitions, that not every complete number is unprecise. We also show that, while a rational number can be coded into a string, a real number has to be coded into a set of strings, and thus an unprecise number is any coded into a semidecidable set. Keywords: uncomputable number, unprecise number, complete number, halting theorem, Turing completeness. §1 Introduction ¶1·Turing (1936) showed that the computable numbers are enumerable when Cantor (1891) had already shown that the real numbers cannot be enumerated. Both together imply that there are infinitely many more uncomputable real numbers than computable numbers. However, in practice, we do not use any uncomputable number. Why? And what does this mean? ¶2·It means that, if we choose randomly a real number, the probability of selecting a computable one is zero. Then, it seems that the uncomputable numbers are the random real numbers. So we use them, frequently, though not any one of them specifically. However, as we will see, that is not the whole story. Real      Computable Uncomputable {Unprecise Random This is doi: 10.6084/m9.figshare.29066705.v3, version 20251020. c 2025 Ramo´n Casares; licensed as cc-by. Any comments on it to [email protected] are welcome. www.ramoncasares.com 20251020 Numbers 2 §2 Two examples ¶1·Perhaps we do not use any specific uncomputable number, but surely we can find them, can’t we? Well, we know of some impossible computations, conspicuously that which solves the halting problem, defined by Davis (1958). Therefore, should computing a number required that we had solved the halting problem, or that we had performed any other uncomputable task, then that number would be uncomputable. ¶2·For example, B= ∞ ∑ n=1 2−S(n)= 2−1+ 2−6+ 2−21 + 2−107 +. . . ≈0.100001000000000000001000000000002 is an uncomputable number since, to compute it completely, with arbitrary precision, we would need to solve the halting problem. S(n) is the busy beaver maximum shifts function, an uncomputable function defined by Rado´ (1962) as the maximum number of steps of all halting computations that a Turing machine with nstates and only two symbols (blank and another one) starting on a blank tape can perform. Notice that this number Bdoes not represent the halting problem as such, but somehow it is only a very peculiar representation of the halting problem of a very specific computing machine on a very special case. ¶3·Fixing the number of symbols to two, the number of states of a Turing machine determines the size of its table. And, see Casares (G), a program is a coded Turing machine table that a particular universal Turing machine can interpret. Then, the number of states nis related to the program length |p|, used for example in Chaitin’s (1975) constant, where p↓denotes that program phalts when it starts on an blank tape: Ω= p∈P ∑ p↓ 2−|p|. Chaitin’s constant Ωis another uncomputable real number. But this number Ω, and any other that uses programs instead of machines, represents the halting problem even more indirectly than B, since it is also mediated by a coding, which is a particular prefix one in the case of Ω. So this number Ωdoes not represent the halting problem as such, but somehow it is only a very peculiar representation of the halting problem of a very specific computing machine on a very special case and very particularly coded. ¶4·Both Band Ωare different from a random number, as for example a binary random number built by flipping a coin to select each of its bits. The difference is that, while we cannot compute any bit of a random number, we can compute some of the bits of B, as shown above, and of Ω, but not all of them. The reason behind this is that the set of the halting computations is computably enumerable, while truly random sequences are not. ¶5·In order to see this in detail, we need some preparation, but since it requires more than one paragraph, it will be the matter of the next section. www.ramoncasares.com 20251020 Numbers 3 §3 The halting set is computably enumerable ¶1·Given an enumeration of a non-empty finite set of non-blank symbols Γ, and every finite set is computably enumerable, we can compute an enumeration of the infinite set Γ∗ of all finite strings drawn from that ordered set of symbols. For instance and canonically, using the shortlex order. Definition: In the shortlex order, strings are primarily sorted by length, with the shortest strings first, and strings of the same length are sorted into lexicographical order, done on the enumeration of the finite set of symbols. Comment: The shortlex order defines a bijection between the strings and the natural numbers, # : Γ∗↔N. For instance, the empty string ⟨⟩ corresponds to zero, and the converse, so #⟨⟩ = 0 and #−1(0) = ⟨⟩. ¶2·Below, we will need to compute an enumeration of the Cartesian product of two infinite sets that are both computably enumerable. The trick is not having to complete one before starting the other one. The triangular enumeration, also known as Cantor pairing function, which is a bijection ∇:N×N↔N, is the canonical way of doing it. Definition: Let a0, a1, a2, a3. . . be an enumeration of set A, and b0, b1, b2, b3. . . be an enumeration of set B. Then the triangular enumeration of A×Bis: (a0, b0); (a0, b1),(a1, b0); (a0, b2),(a1, b1),(a2, b0); (a0, b3),(a1, b2),(a2, b1),(a3, b0); . . . In other words, pair (ax, by) is pair number i,pi, where: i=∇(x, y) = x+(x+y)(x+y+ 1) 2, s=∇−1 s(i) = ⌊−1 + √8i+ 1 2⌋, x=∇−1 x(i) = i−s(s+ 1) 2, y=∇−1 y(i) = s−x . ¶3·Definition: To define computation, we need the equation of Turing completeness, see Casares (G): ∃U,∀P,∀d:←−−−− U⟨p| d⟩=P⟨d⟩, where: ◦ P is a Turing machine, ◦d∈Γ∗ Pis an input string to P, ◦ P⟨d⟩ ∈ Γ∗ Pis the corresponding output string, or ∞/∈Γ∗ Pif it does not halt, ◦ U is a universal Turing machine, ◦ d∈Γ∗ Uis the string dcoded in the language Limplemented by U, ◦p∈Γ∗ Uis the program that codes Pin the language Limplemented by U, so p= P, ◦the |represents an end of program symbol or, in general, the composing operation of the language Limplemented by U, as cons or Merge, ◦ U⟨p| d⟩ ∈ Γ∗ Uis the output string of U, which is coded in the language Limplemented by U, or ∞/∈Γ∗ Uif it does not halt, and ◦the left pointing arrow on top denotes the corresponding decoding, ←−  d=d, which leaves ∞unchanged, ←− ∞=∞. www.ramoncasares.com 20251020 Numbers 4 ¶4·Definition: Any language implemented by a universal Turing machine Uthat satisfies the equation of Turing completeness is a complete language, denoted L, also known as a Turing complete language. Definition: In the complete language Limplemented by the universal Turing machine U, the string between angled quotes ⟨p| d⟩expresses c, which is the computation that applies coded data  dto program p. Definition: The halting set is the set of all halting computations. ¶5·Note that, while in the right hand side of the equation of Turing completeness, dis any string of symbols of P, in the left hand side, what is on the tape is not any string of symbols of U, but a well-formed formula, or sentence, of the language Limplemented by U. Therefore, the equation of Turing completeness requires parsing the left hand side string between angled quotes, implying that it has to be always possible to decide ◦whether a string of Uis a well-formed formula ⟨p| d⟩of Lor not, which requires to be always possible to decide both: ◦whether a string of Uis a program pof Lor not, and ◦whether a string of Uis properly coded data  dof Lor not. In other words, the syntax of the language Limplemented by U, which is the set of its sentences, denoted ΣL, is decidable. And, since the sentences of Lare computations, c=⟨p| d⟩, the semantics of a complete language expresses computations; the meaning of sentence ⟨p| d⟩is P⟨d⟩. But, because we are finite, we can only reach the meaning of the halting computations, so for us semantics, denoted ΨL, is the halting set. We will call any non-halting computation a paradox, implying that paradoxes are syntactically correct sentences that do not belong to semantics. ¶6·Theorem 1:The set of all computations is computably enumerable. Proof: The syntax of the language Limplemented by Uis decidable, and every wellformed formula of Lis a computation. Therefore the set of all computations is decidable, and then, as shown by Post (1944), both itself and its complement (in the set of all strings of symbols of U) are computably enumerable. qed Comment: Practically, we can enumerate the finite strings of Uusing the shortlex order. Then we can order the set of programs, thus. Take the next string in the enumeration of the strings of U, and determine whether it is a program of Lor not: if it is, append it to the enumeration of programs and go to the next one; if it is not, discard it and go to the next one. Similarly, we can order the set of coded strings. And now, given the enumeration of programs and the enumeration of coded data strings, we can use the triangular enumeration to build the enumeration of computations. ¶7·Theorem 2:The set of all halting computations is computably enumerable. Proof: Since the set of computations is computably enumerable, by Theorem 1, let us denote computation number cas cc. Now we define the set of runnings as the Cartesian product of the set of computations and the natural numbers. Then the generic running is the ordered pair (cc, s), where srepresents a number of computing steps, so s∈Nwith its natural order. We evaluate (cc, s) to 1 if computation cchas halted after running its first ssteps, and to 0 otherwise. Finally, we build the triangular enumeration of runnings and, every time we get a pair (cc, s) that evaluates to 1, we append ccto the enumeration of the halting computations, if it was not already in. qed Comment: In fewer words, the halting set is computably enumerable. Or, in even less words, semantics is computably enumerable. www.ramoncasares.com 20251020 Numbers 5 §4 Halting theorem ¶1·Without loss of generality, we will use the complete language Limplemented by the universal Turing machine Uwith its canonical enumerations # and ∇for the proof of the halting theorem; its first version is in Turing (1936) §8, see §5.3. Theorem 3:No program can decide for every computation whether it will halt or not. ¶2·Proof: Just before Theorem 1, we have already seen: ◦that the set of coded strings Σ d Lis decidable and then computably enumerable, so we will refer to coded string number das  dd; ◦that the set of programs Σp Lis decidable and then computably enumerable, so we will refer to program number pas pp; and ◦that the set of computations ΣLis decidable and then computably enumerable, so we could refer to computation number cas cc, where cc=⟨pp| dd⟩if c=∇(p, d). ¶3·We will set a Cantor’s diagonal argument to show that there is not any Turing machine Hthat takes any arbitrary computation as input and every time it outputs, in a finite number of computing steps, a string expressing whether the computation will halt or not, say the string  d1if it will halt, and  d0if it will not halt. ∃H,∀p,∀ d{H⟨p| d⟩= d1if U⟨p| d⟩ =∞ H⟨p| d⟩= d0if U⟨p| d⟩=∞ ¶4·Now, for the sake of the argument, let us assume that Hexists. Then the following matrix of  d1and  d0string values could be computed (without got stuck in a non-halting computation) using the triangular enumeration ∇on every computation. H⟨p0| d0⟩ H⟨p0| d1⟩ H⟨p0| d2⟩. . . H⟨p0| dd⟩. . . H⟨p1| d0⟩ H⟨p1| d1⟩ H⟨p1| d2⟩. . . H⟨p1| dd⟩. . . . . .. . .. . ..... . .... H⟨pp| d0⟩ H⟨pp| d1⟩ H⟨pp| d2⟩. . . H⟨pp| dd⟩. . . . . .. . .. . ..... . .... However, the row for program q, which negates the diagonal, would not be in the matrix. q:∀n∈N{U⟨q| dn⟩= d1if H⟨pn| dn⟩= d0 U⟨q| dn⟩=∞if H⟨pn| dn⟩= d1 Since, ∀p∈N,q=pp, then program qcannot exist. But program qwould exist if the program for H, denoted h, existed, which would be the case if Hexisted as assumed. Therefore, the assumption was false. ¶5·Then, in the complete language Lof the universal Turing machine U, a program h that decides for every computation whether or not it will halt cannot exist. qed ¶6·Corollary: The halting theorem says that the halting set is undecidable. Therefore, in every complete language L, syntax ΣLis decidable but semantics ΨLis undecidable. Comment: In terms of Post (1944), the halting set ΨLis computably enumerable, but not its complement. Neither its complement in the set of strings, Γ∗ U\ΨL, nor its complement in the set of sentences, ΣL\ΨL, is computably enumerable, though both are enumerable. Then, more precisely, the halting set is semidecidable, see §7¶2. ¶7·With these tools, we are ready to build uncomputable numbers based on the unsolvability of the halting problem, as Band Ω. So it is time for a new section. www.ramoncasares.com 20251020 Numbers 6 §5 Three complete numbers §5.1 Computable ¶1·In Theorem 2, we have used the triangular enumeration of runnings, (cc, s), of the complete language Lto compute the following matrix of bits. (c0,0) (c0,1) . . . (c0, s). . . (c1,0) (c1,1) . . . (c1, s). . . . . .. . ..... . .... (cc,0) (cc,1) . . . (cc, s). . . . . .. . ..... . .... Definition: The triangular enumeration of the matrix of runnings defines number R, which uses every bit in the matrix, where i=∇(x, y) and (x, y) = ∇−1(i): R= ∞ ∑ i=0 2−(i+1)(cx,y). ¶2·As number Rincludes every bit in the matrix of runnings, it could seem that it contains all the information that the halting problem oracle needs, see Turing (1938), suggesting that number Ris not computable. However, it is computable! ¶3·Definition: There are several ways of defining what a computable real number is. Minsky (1967), page 159, defines “a computable number to be one for which there is a Turing machine which, given non its initial tape, terminates with the nth digit of that number.” Translated to the complete language L, a number is computable if there is a program that, when coded data  dnis applied to it, it halts with the nth figure of that number coded on the tape. Then, every computable number has to be defined by an always halting program, which is one that halts on every (syntactically correct) input. ¶4·Theorem 4:Number Ris computable. Proof: When computing bit nof number R, the program has first to set the stage, which requires computing ∇−1(n)=(c, s) and ∇−1(c)=(p, d), then do the actual running of computation cc=⟨pp| dd⟩for ssteps, and finally tidy up everything to answer string  d1if the computation has halted, or string  d0if it has not halted. Since the program computing number Ralways (for every  dn) halts after a finite number of computing steps, splus setup and cleaning, then number Ris computable. qed ¶5·Definition: The complete numbers are those that only a universal Turing machine can compute. Then we can also say that the complete numbers can only be defined in a complete language. Numbers B,Ωand Rare complete numbers. Loosely speaking, these numbers require a complete language because they cannot be calculated by a single program, given that we need to apply different programs to compute different bits; in fact, to compute a complete number completely we would need to apply all of them. ¶6·Number Rfails to be an uncomputable number because every running is limited to a number of steps, and thus there is no chance of closing an infinite loop. This failure means that the intuitive idea that ‘those numbers that require a complete language to be defined are uncomputable’ does not work. My wrong intuition was that requiring a complete language is the same as requiring self-reference and that self-reference is bound to close infinite loops. We will deal with that intuition below, in §5.3. www.ramoncasares.com 20251020 Numbers 7 §5.2 Uncomputable ¶1·Definition: We can define an uncomputable number Hsimply by coding the halting computations into a real number between 0 and 1: given a complete language Lwith its canonical enumerations # and ∇, bit nof number His 1 if computation cnhalts (denoted cn↓), and 0 if it does not halt: H= n∈N ∑ n:cn↓ 2−(n+1) . ¶2·To calculate number Hwe can start with number 0, that is, with all of its bits set to 0, and following the procedure used to prove that the halting computations are computably enumerable, see Theorem 2, every time we find a computation cithat halts, ci↓, we set bit ito 1. Since the procedure can go on infinitely, we can always add new bits 1 to number H, so we can always make it more precise. However, bits will not be added orderly, that is, having determined that bit jis 1 does not grant us that we could not find later on that another bit k < j is 1. So number His computably approximable, though it is not left-computable. ¶3·Theorem 5:Number His not computable. Proof: If number Hwere computable, then there would be a program that, given coded data  dnon its initial tape, would halt with the nth bit of number Hcoded on the tape, let us call it program h. Then, computing the nth bit of number Hwould be done by computation ⟨h| dn⟩, which, if n=∇(p, d), would require deciding whether computation cn=⟨pp| dd⟩will halt or not. Since ngoes through every natural number and ∇is a bijection, then program hwould have to decide for every computation whether it will halt or not. However, the halting theorem says, see Theorem 3, that such a program h cannot exist. Therefore, number His not computable. qed ¶4·Should we could compute every bit of number H, then program hwould exist, but since program hcannot exist, then we cannot compute every bit of it. So number His not computable because we cannot compute all of its bits. However, we can compute some bits of number H, for example those corresponding to simple computations that halt. Then, number His not a random number either, since we cannot compute any of the bits of a random number, that is, none of them. ¶5·Definition: Then we will say, by definition, that a number is unprecise if we can compute some of its bits, where ‘some’ means ‘neither none nor all’. Numbers B, Ωand Hare unprecise numbers. Under this definition, the numbers that result from measurements are unprecise, by design; for example, we write 3.25 ±0.05 m to express purposely that the centimeters digit is random. In this paper, we are not interested on these numbers that are intentionally defined unprecise, so we will only consider those unprecise numbers that are unprecise because of computing limitations. ¶6·Number His a complete number, because computing it requires computing every computation. Comparing number Hto unprecise numbers Band Ω, number His more general, since it is not limited to two symbol computations on empty strings. And compared to number Ω, number His not limited to prefix languages. Number His the canonical representation of the halting set of the complete language Limplemented by the universal Turing machine U; in short, number Hcodifies ΨL, the semantics of L. In still other words, number His the canonical coding of the halting problem oracle, see Turing (1938), of the complete language L. www.ramoncasares.com 20251020 Numbers 8 §5.3 Turing’s intuition ¶1·Turing (1936), last paragraph of subsection II of section §9 in page 253, defines the uncomputable number δ: It must be remembered that we have attached rather a special meaning to the phrase “ Adefines α”. The computable numbers do not include all (in the ordinary sense) definable numbers. Let δbe a sequence whose n-th figure is 1 or 0 according as nis or is not satisfactory. It is an immediate consequence of the theorem of §8that δis not computable. It is (so far as we know at present) possible that any assigned number of figures of δcan be calculated, but not by a uniform process. When sufficiently many figures of δhave been calculated, an essentially new method is necessary in order to obtain more figures. ¶2·Here, Turing’s method to define the uncomputable number δwas adapted to define our unprecise number H. Instead of satisfactory numbers, which describe non-halting computations, number Huses halting computations, and accordingly it uses the halting theorem instead of Turing’s theorem of §8. This adaptation updates Turing. In a sense, the adaptation is not necessary, since it just translates (though it is not a full translation, but only a recoding) from the engineering always running logic of Turing, where a halted computer with its Blue Screen of Death should be avoided, to the opposite always halting logic, which is much more convenient philosophically because it prevents the problems of the infinity. ¶3·The adaptation is currently so pervasive that Turing’s theorem of §8 is usually referred to as the halting theorem without further commentaries or explanations. In what follows, we will assume the always halting logic, and consequently, when referring to Turing’s unprecise number δ, we should remember that, because of its opposite logic, we have to swap ‘running’ for ‘halting’. ¶4·In any case, Turing’s intuition, as it is expressed in the very last sentence of the cited paragraph, which works for numbers B,Ω,δand Hbecause all four are complete and unprecise, is not right because it does not work for number R, which is complete and computable. And then it is not always true that needing every possible method in order to obtain more figures makes a number unprecise, and then uncomputable. ¶5·Theorem 6:Not every complete number is unprecise. Proof: Because number Ris complete and is not unprecise. It is complete because of its definition, which requires computing every possible computation, and it is computable as shown by Theorem 4. Being computable, number Ris not unprecise. qed ¶6·I was also wrong believing that every complete number is unprecise, see §5.1¶6. A complete language is one that implements the whole semantics of computing, and therefore it is full-self-expressible, see Casares (G). Then, any concept that requires a complete language to be defined, as for example each complete number, requires the full semantics of computing, including self-reference. Self-reference can easily generate contradictions, the simplest one being the liar paradox, this sentence is not true, but, as number Rand primitive recursion show, it is not true that every application of selfreference creates a contradiction. In particular, number Rshows that keeping finiteness is the proper way for avoiding paradoxes. www.ramoncasares.com 20251020 Numbers 9 §6 Kinds of numbers §6.1 Naturals ¶1·How can we classify the numbers from a computing point of view? Let us start from the simplest ones, the counting numbers, also known as the natural numbers, N. ¶2·Any natural number n∈Ncan be written as a finite string of the numerals of the base. In fact, the shortlex order defines a bijection between the strings and the natural numbers, see §3¶1. In base one, which uses only one figure symbol, let us write it 0, the number is represented by the length of the string, so the empty string ⟨⟩ represents number zero (#⟨⟩ =|⟨⟩| = 0), string ⟨0⟩represents number one (#⟨0⟩=|⟨0⟩| = 1), string ⟨00⟩represents number two (#⟨00⟩=|⟨00⟩| = 2), and so on. ¶3·In base two, let us use symbols 0 and 1 for the bits, with 0 <1, zero is written ⟨⟩ (#⟨⟩ = 0), one is written ⟨0⟩(#⟨0⟩= 1), two is written ⟨1⟩(#⟨1⟩= 2), three is ⟨00⟩ (#⟨00⟩= 3), four is ⟨01⟩(#⟨01⟩= 4), five is ⟨10⟩(#⟨10⟩= 5), six ⟨11⟩(#⟨11⟩= 6), seven ⟨000⟩(#⟨000⟩= 7), and so on. ¶4·Also in base two, we can use the typical positional notation, which makes easier addition and other operations but which is less compact than our canonical notation, since left zeroes are redundant. In base two positional notation, strings ⟨⟩,⟨0⟩,⟨00⟩, and so on, all represent number zero; one can be written ⟨1⟩,⟨01⟩,⟨001⟩and so on; the shortest way to write two is ⟨10⟩; and so on. ¶5·We can continue with base three, four, and so on, but the conclusion is always the same: any natural number can be written as a finite string of symbols. §6.2 Integers ¶1·Taking any of the notations to write natural numbers, it is enough to add an optional prefix sign, typically a minus symbol (−), to write any integer number z∈Z. For example, if in binary positional notation the string ⟨1101⟩represents number thirteen, then ⟨−1101⟩represents minus thirteen. ¶2·Now the conclusion is: any integer number can be written as a finite string of symbols. §6.3 Rationals ¶1·Any rational number q∈Qcan be generated by a finite state machine. Disregarding the optional sign symbol, a fraction is simply an ordered pair of natural numbers, so it can be written as two separate finite strings, for instance 23/14. And, when expanded, every rational numeral, in any natural base, is a regular expression: a finite string for its whole part (w), a literal point (.) separating the whole part from the fractional part, which is a finite prefix string (p) followed by a infinitely repeated finite string (r), where the three strings can be empty; a single point represents zero. For example, in positional base ten, 23 14 = 1.6428571428571428 . . . = 1.6428571 , where w=⟨1⟩,p=⟨6⟩, and r=⟨428571⟩, or in general the regular expression w.pr*, where the Kleene star *is a postfix meaning forever. ¶2·Therefore a rational number can be expressed as a fraction, which is just an ordered pair of numeral strings, or as its expansion, which is a regular expression. In any case, the conclusion is: any rational number can be generated by a finite state machine.