2e:null 2f:["$","title",null,{"children":"Computable Real Numbers | Real Numbers | Observable"}] 34:T450,--- --- --- --- --- --- --- --- --- ## Number Objects In our first post, "[Number Objects](https://observablehq.com/@dlaliberte/number-objects)", we created a system in which each number is represented by an instance of the `Real` class, which corresponds to a leaf node in a binary tree. The leaf node for a given a number represents a finite prefix of digits for the number, determined by the path from the root node down to the leaf node. Each number object will correspond to a single leaf node, and vice versa, so there is always a **one-to-one correspondence between number objects and leaf nodes of the binary tree**. Each number object created by the Real class also references two other numbers that correspond to its nearest neighbors in the binary tree. This forms a **doubly-linked list of all known numbers in the enumeration, ordered by their numeric value**. When a new number is created and its leaf node is added to the binary tree, we crawl back from the leaf node to find the next lower number, and insert the new number between that number and the next higher number. 35:T457,function generateChampernowneNumber(depth) { const numbers = []; const nums = [...Array(depth + 1).keys()].slice(1); // 1..depth const digitsToAdd = nums.map((num) => num.toString(2).split("")).flat(); // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); // Generate 0 and 1 branches. numbers.push(Zero.construct(rootNode.addDigit("0"), 0)); numbers.push(One.construct(rootNode.addDigit("1"), 1)); const champ = Real.construct( rootNode, numbers.length, "Champernowne", digitsToAdd ); numbers.push(champ); // Make sure we don't generate more numbers than the pregenerated Champernowne digits. // Otherwise the random digit generator will kick in. while (numbers.length - 2 < digitsToAdd.length) { const parentNode = champ.node; const nextDigit = champ.addNextDigit(); const newNode = parentNode.addDigit(nextDigit == "0" ? "1" : "0"); const newNum = Real.construct(newNode, numbers.length); // not right yet: `-${nums[numbers.length - 3]}` numbers.push(newNum); } return { tree: rootNode.traverseTree(), numbers }; }36:T458,function generateCopelandErdosNumber(depth) { const numbers = []; const nums = primes.slice(0, depth); const digitsToAdd = nums.map((num) => num.toString(2).split("")).flat(); // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); // Generate 0 and 1 branches. numbers.push(Zero.construct(rootNode.addDigit("0"), 0)); numbers.push(One.construct(rootNode.addDigit("1"), 1)); const copelandErdos = Real.construct( rootNode, numbers.length, "Copeland-Erdos", digitsToAdd ); numbers.push(copelandErdos); // Make sure we don't generate more numbers than the pregenerated Copeland-Erdos digits. // Otherwise the random digit generator will kick in. while (numbers.length - 1 < digitsToAdd.length) { const parentNode = copelandErdos.node; const nextDigit = copelandErdos.addNextDigit(); const newNode = parentNode.addDigit(nextDigit == "0" ? "1" : "0"); const newNum = Real.construct(newNode, numbers.length); // not right: nums[numbers.length - 3] numbers.push(newNum); } return { tree: rootNode.traverseTree(), numbers }; }37:T5b0,function generateLiouvilleNumber(depth) { const numbers = []; const digitsToAdd = new Array(depth + 2).fill('0'); let facIndex = 1; let fac = 1; // == fac(facIndex); digitsToAdd.forEach((digit, index) => { if (index+1 == fac) { facIndex++; fac = fac * facIndex; digitsToAdd[index] = '1'; } //db('digits', digitsToAdd); }); // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); // Generate 0 and 1 branches. numbers.push(Zero.construct(rootNode.addDigit("0"), numbers.length)); numbers.push(One.construct(rootNode.addDigit("1"), numbers.length)); const liouville = Real.construct( rootNode, numbers.length, "Liouville", [...digitsToAdd] // Must clone digits since this arg is modified by side effect. ); numbers.push(liouville); // Make sure we don't generate more numbers than the pregenerated digits. // Otherwise the random digit generator will kick in. //db('numbers.length', numbers.length); while (numbers.length + 1 < digitsToAdd.length) { const parentNode = liouville.node; const nextDigit = liouville.addNextDigit(); const newNode = parentNode.addDigit(nextDigit == "0" ? "1" : "0"); const newNum = Real.construct(newNode, numbers.length); numbers.push(newNum); // db('numbers.length', numbers.length); // db('digits.length', digitsToAdd.length); } return { tree: rootNode.traverseTree(), numbers }; } 38:T435,function generateOneOverPhi(depth) { const numbers = []; const sqrt5 = Math.sqrt(5); function binet(n) { return Math.round( (Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n)) / sqrt5 ); } function fib(n) { return binet(n); } const indices = [...Array(depth).keys()]; // .slice(3); const fibNums = indices.map((i) => fib(i + 3)); // fib(3..depth+3) const ratios = indices.map((i) => ratio((i == 0 ? 1 : fibNums[i - 1]), fibNums[i], 2) ); // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); // Generate 0 and 1 branches. let index = 0; numbers.push(Zero.construct(rootNode.addDigit("0"), index++)); numbers.push(One.construct(rootNode.addDigit("1"), index++)); const goldenNums = ratios.map((q, i) => { // console.info('pattern', pattern); const num = Rational.construct( rootNode, index++, `${q.dividend}/${q.divisor}`, q.fraction, q.cycle ); numbers.push(num); return num; }); return { tree: rootNode.traverseTree(), numbers }; }39:T875,## Computable vs Uncomputable Numbers We would like to be able to describe the exact value of _any_ real number with a function that can generate as many of its digits as requested. We know how to easily compute as many digits of any rational number as we want. And we can define more complicated functions for any "algebraic" number. We can also do the same for any irrational number as long as we have a function that will generate as many digits as requested, as we showed in the above examples. But we have a problem because it is generally accepted that not all real numbers are "[Computable Numbers](https://en.wikipedia.org/wiki/Computable_number)", and worse, that the vast majority of real numbers are uncomputable. There are two ways this belief is justified. 1. The number of all possible finite-length programs that could be used to generate numbers is a countable infinity. The way to understand this is by thinking of each program as a finite-length string of ASCII characters and we can map those characters to digits in a base 128 number system. This means that each program corresponds to a natural number, so we can enumerate all possible programs of this form by enumerating the natural numbers and generating the corresponding programs. For each program, if it runs at all, it can be used to compute, at most, a countable set of real numbers. Therefore, the largest set of numbers that could possibly be computed this way with all possible programs is also countable. However, if the set of real numbers is in fact uncountable, then there must be many more real numbers that cannot be computed by any possible finite-length program. 2. A second issue involves whether an arbitrary programs intended to generate digits of a number actually does so. It is certainly the case that, given any arbitrary program, regardless what it does, it is not possible to know whether it will actually complete the computation in a finite amount of time due to the "Halting Problem". This means that if the only way to compute some numbers is with program that we cannot prove will do so, that would make the number it was trying to compute uncomputable.3a:T8eb,However, a weakness in this argument is that it assumes it is impossible to find _another_ function that we _can_ prove will terminate while generating the same digits of a Chaitin constant. If it is possible to find such a function, then the number would no longer be uncomputable. One clear obstacle with this counter-argument is that, because we cannot know exactly what this Chaitin constant is, it would seem that it is impossible to generate its digits with _any_ function. However, if we could somehow enumerate an entire _range of numbers_ that must include this number, then we will avoid this problem. But, of course, that would be an impossible task if any range of real numbers contains an uncountable, continuum of numbers. We'll deal with that argument later, but for now, note that it would be a circular argument to use the uncountability of Reals to defend the existence of uncomputable numbers, which is then used to defend the uncountability of the Reals. In general, if a function is intended to return the digits of a number but is actually uncomputable, we should recognize it as an improper function for generating the digits of that number. However, the failure of one function to generate the digits of a number does not mean that it is impossible to compute those digits in some other way. Therefore, any _function_ might be uncomputable, but this does not imply that the number we intended to compute with the function is also uncomputable. It is always possible that there might be a different function that can compute any desired number of digits of the same number in a finite amount of time. So, can we prove that there is a function which can generate as many digits of any number as requested? Alternatively, can we prove that there is no possible function which can compute some numbers without relying on the uncomputability of the Reals? We have to ask, however, how do we specify a number that we want to compute? How do we know what a number is unless we relate it to other numbers using some function? It is true that, if the only way we can define some numbers is by specifying a function that might not halt, then we have a problem. However, it is not clear how we would prove that this is the _only_ way to define such a number. 3b:T9ca,### Abstraction of Numbers vs Functions used to Define Numbers The general problem with the usual idea of uncomputable numbers is that it conflates two concepts: the abstraction of numbers and the functions used to define them or to compute their digits. These concepts are not the same. Numbers should be considered independently of the functions that compute them primarily because there are multiple functions that can be used to compute the very same numbers. Part of the confusion stems from how we define some of the properties of sets of numbers based on the functions we typically use to compute them. This is what we do for the set of natural numbers, in which each natural number is computed by the simple function of adding one to the preceding number. And we can do this for the set of rationals, in which each rational number can be computed to any degree of precision from the ratio of two natural numbers. And we can also do something similar for the set of algebraic numbers, which are computed by iterating over the solutions to a sequence of polynomials with integer coefficients. Our knowledge of some particular functions that we can use to compute a set of numbers allows us to infer properties of this set of numbers, such as the property of being countable, but if we lack the knowledge of how to produce a function that computes some set of numbers, that should not imply that there is necessarily no such function that computes those numbers. The transcendental numbers are the set of irrational numbers excluding the algebraic numbers, and we only know how to compute a relatively small subset of them. There are vastly more transcendental numbers for which we have no knowledge of how to compute their values by employing the usual mathematical tools, but that lack of knowledge doesn't mean it is impossible to come up with new ways to compute those numbers. If we limit the mathematical tools we can use in the functions that define numbers, then indeed, we may be unable to compute some numbers. For example, irrational numbers were considered "uncomputable" in the past because we only had the tools of rational arithmetic. This means that we could "define" numbers like the square root of 2, but we could not compute their values using ratios of natural numbers. To overcome this limitation, we invented new tools, such as infinite series, to deal with the infinite calculations required to effectively "compute" such numbers to any desired degree of precision. 3c:T586,### Any Number vs Every Number Although the infinite precision of each irrational number in terms of its digit sequence cannot be completely known, it is clear that as long as we have a terminating function that computes as many digits as we need, we can declare the number to be computable. In the following section, we will show that this is possible for any arbitrary real number. It is important to note that the ability to generate as many digits as requested for any arbitrary number does not imply that we can enumerate every possible real number, including those that might be considered uncomputable. In other words, even if we can show that any arbitrary number is computable given a function for generating its digits, and that this implies that every real number with a similar function is computable, it is a different and more difficult problem to enumerate every possible number. In order to consider the possibility of enumerating all real numbers, we must reject the notion of the necessary existence of uncomputable numbers. If such numbers necessarily exist, then we could never encounter them in any enumeration of real numbers, and therefore, no enumeration of all real numbers would be possible. However, even if we cannot enumerate all real numbers, this does not necessarily imply that the reason for our inability to do so is that there is an uncountable subset of uncomputable numbers.3d:T723, You might agree that randomly generating the digits of a single real number makes it computable, but argue that this doesn't mean we know how to do the same for _every_ real number, since we have no way of enumerating all of them to make sure we haven't missed any. It is true that, at this point, we don't know how to enumerate all the real numbers, and Cantor argues that it is impossible to do so. It is important to note that, when we say that we are computing the digits of real numbers randomly, we are not claiming that we can generate and enumerate _every possible real number_. We are only showing that we can compute all the digits of _a single random real number_ by choosing the digits randomly. We are only generating one random real number at this time, but we do not need to enumerate all real numbers in order to be certain that we can generate _any single real number_. But, first things first. Let's just agree that we can compute any single real number. By the way, some people argue that it is impossible to compute a _truly_ random number because by definition, a truly random number cannot be computed. We will discuss this further in the section on pseudo-random number generators. However, whether or not this number is truly random, we can agree that it does compute _some_ real number. 3e:T433,## Depth-first Generation of One Random Real Number We can generate a random real number by choosing its digits randomly. In binary, we can choose each digit to be either a '0' or '1', and repeating this process allows us to theoretically compute all the digits of one real number. Below is an example of how we can visualize the depth-first generation of just one random real number, named 'X'. By default, the X number is pre-generated, which means that a unique number object is created and initialized, not that its precise value is known at the time it is created because that precise value is never known since we can never finish generating all of the digits. For each additional digit that we add to the number X, we also generate another number with the same prefix but the opposite digit, and this process is repeated until the selected Depth is reached. Every time you click the "Regenerate" button, it starts over and generates a different number for X. Decreasing the Depth will remove digits and increasing the Depth again will add more random digits. 3f:T707,// Generate one number and others that branch off all of its prefixes. function* generateOneRandomNumberDepthFirst( initialDepth = 32, pregenerateX, animate ) { let numNumbers = initialDepth; // + 2; // For Zero and One const numbers = []; let index = 0; // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); const randomDigits = generateNRandomDigits(numNumbers).slice(); // db('nRandomDigits', nRandomDigits); let currentNum; let parentNode = rootNode; let nextDigit = randomDigits.shift(); pregenerateX = pregenerateX == "noX" ? false : pregenerateX; // Generate the number for X, which will always be currentNum currentNum = Real.construct(rootNode, index++, pregenerateX ? "X" : `X${index-1}`, [nextDigit]); numbers.push(currentNum); while (numbers.length < numNumbers) { let newNode; parentNode = currentNum.node; nextDigit = randomDigits.shift(); if (pregenerateX && pregenerateX !== "noX") { // Add nextDigit to curentNum currentNum.addDigit(nextDigit); // Add other digit to parentNode to get newNode. newNode = parentNode.addDigit(nextDigit == "0" ? "1" : "0"); } else { // Add other digit to currentNum currentNum.addDigit(nextDigit == "0" ? "1" : "0"); // Add nextDigit to get newNode. newNode = parentNode.addDigit(nextDigit); } // console.info('newNode', newNode); const newNum = Real.construct(newNode, index++, pregenerateX ? "" : `X${index-1}`); numbers.push(newNum); if (!pregenerateX) { currentNum = newNum; } if (animate) { yield { tree: rootNode.traverseTree(), numbers }; } } // Return list of nodes by traversing the binary tree. return yield { tree: rootNode.traverseTree(), numbers }; }40:Tb7f,### Real.generateNewRandomNumber Here is a more detailed summary of the generator of a single random number. The `Real` class, used for creating instances of numbers, has a static function called **`Real.generateNewRandomNumber`** that generates one new random number by executing the following process. (This is similar to the process used above by the function `generateOneRandomNumberDepthFirst`.) Given the current state of the binary tree representing the digits of all the numbers generated so far, typically starting with only the bounding numbers for 0 and 1, we will choose a sequence of random digits while crawling out from the root node of the binary tree, checking each digit one at a time in the corresponding nodes of the tree. For each digit, we will do the following steps. Initially the **current node** is the root node. 1. Choose the **next random digit** and look up that digit in the **current node** of the binary tree. 2. If we find a **non-empty branch**, it might go to a leaf node or a non-leaf node. 3. If the branch goes to a **non-leaf node**: * Set the **current node** to this non-leaf node. * Continue crawling the binary tree by going back to step 1. 3. If the branch goes to a **leaf node**, it corresponds to an existing number: * First we **add one more digit to that number**. * Set the **current node** to the node (which was a leaf node, but now no longer is). * Then we continue choosing more random digits for the number we are still trying to create (back to step 1). * Note that once we bump into a previously existing number, we will keep bumping into that same number until we find an empty branch. * When adding a digit to a Real number, it adds a random '0' or '1' digit by default. * When adding a digit to the numbers Zero or One, we always add a '0' or '1' digit respectively. * The new digit added to the existing number is guaranteed not to create a conflict with any other number since every number is independent of all other numbers once it has been created. 4. Once we finally find **an empty branch**: * We add a new node to the binary tree. * We also create a new number object that references this new node. * This number object represents the sequence of digits generated so far for this number. * Continue to the final task. 5. As a **final task** when creating a new number, we also **find the next smaller number** in the binary tree, and insert the new number in the doubly-linked ordered list of numbers between that previous number **and its next larger neighbor**. * To find the next smaller number, we must crawl back toward the root node, where at each node, the '0' branch is not to the node we were just visiting; then we crawl out to the largest number in the subtree of that '0' branch. * Note that the number we bumped into previously, if any, will be either the next number or previous number compared to the new number.41:T67b,## Random Irrationals vs Random Rationals The generation of random digits of a number seems likely to result in an irrational number. But could it result in a rational number? It might be argued that the resulting number is "infinitely more likely" to be an irrational number, since our current understanding is that there are _many_ more irrational numbers than rational numbers, and thus the probability of randomly generating a rational number from an infinite sequence of random digits approaches 0. But note that the probability of generating any specific _irrational_ number also approaches 0. In fact, it should be clear that it is equally likely that we will generate _any_ real number (between 0 and 1 in our case), regardless whether it is rational or irrational. But that is still different from the question of whether the specific random number we generate is more likely to be rational or irrational. Some people would claim that the probability of generating any specific real number is _actually_ 0, not just that it _approaches_ 0. But since we do compute _some_ real number, whatever it is, how can the probability be actually 0 that we will generate that number or any other specific number? If the probability of generating any specific number is actually 0, then it would seem to be impossible to generate any numbers at all. In other words, if we generate as many digits as needed for a specific number, then we will generate that number. Therefore, the probability of generating that number cannot be 0, since otherwise it would be impossible to generate. This is also true for any other number that we can generate this way.42:T652,## Random Numbers Chosen Independently Could Collide We need to consider the possibility that any random number we generate could be the same as a previously generated number. This possibility is actually intentional because it affirms that _any_ number, including a previously generated number, or a rational number, could be generated. If the probability of generating the same number twice is actually zero, then there is no possibility of a collision. But if a collision is possible, the probability of generating the same number twice must be greater than zero. However, we have a problem if the possibility of a collision means two different numbers with identical values might be generated during the same enumeration. This would be a problem if we have specific numbers representing 0 and 1, for example, as we do in the above examples. There is admittedly a non-zero, infinitesimal probability that the random real number we generate could be identical to 0; this would happen if _every_ random digit chosen is a '0', in which case the system would loop forever waiting for a '1' digit to be chosen randomly so that the number would be different from 0. We might try to avoid this problem by never including specific numbers, like 0 and 1, but the very same problem could occur if we are only generating two random numbers, and no specific numbers. So we have to admit that by randomly choosing numbers this particular way, we cannot guarantee that we will never have a collision between two numbers. We'll have to find another way of generating random numbers that avoids the possibility of collisions.43:T473,// Generate one number and others that branch off all of its prefixes. function generateNRandomNumbers(depth = 32, n) { const numbers = []; let index = 0; // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); // Generate 0 and 1 branches. const zero = Zero.construct(rootNode.addDigit("0"), index++, "Zero"); numbers.push(zero); const one = One.construct(rootNode.addDigit("1"), index++, "One"); numbers.push(one); // let done = false; // while (!done) { // while (numbers.length >= n + 2) { // // Truncate to first n + 2 // numbers.pop(); // } while (numbers.length < n + 2) { const currentNum = Real.construct(rootNode, index++); numbers.push(currentNum); } // return yield { tree: rootNode.traverseTree(), numbers }; for (let d = 0; d < depth; d++) { for (const num of numbers) { num.addNextDigit(); } // return yield { tree: rootNode.traverseTree(), numbers }; } // done = true; // } // Return list of nodes by traversing the binary tree. return { tree: rootNode.traverseTree(), numbers }; }44:T821,As discussed above, the generator could potentially loop forever while it is trying to find an unoccupied leaf node for a new number. The more random numbers we have already added to the tree, the longer the search will have to continue. On average, the depth of the tree will be about `log base 2 of N` for `N` numbers, but in the extreme case, there is no upper limit to how long the search must continue since a new random number could happen to be identical to a previously added number. However, once each number has been created and added to the tree, then it is independent of all the previously generated the numbers. If you increase the option above for "Number of Additional Digits" that are added to all numbers, then you can see that adding more digits to any number, once it has been created, does not affect any other number. Ignoring the problem of collisions for now, we can consider what would happen as the number of randomly created numbers approaches infinity. In general, the number of random numbers being created in this way could be increased indefinitely. Even if we never explicitly add more digits to each number after it has been created, each number will likely be extended with more digits as a countable infinity of new numbers are added. This process continues indefinitely, with the number of random numbers generated becoming increasingly large as it _approaches_ an infinite number of real numbers. This would mean that we can _potentially_ compute any real number given an algorithm for generating digits randomly. It's important to note that generating numbers using this method does not necessarily mean that all real numbers between 0 and 1 will be generated, nor does it guarantee that each number we do generate will have all its infinite number of digits added to it. In addition to the potential for collisions, if a number is never extended beyond a finite prefix of digits, this would mean we are missing all the numbers that extend from that same prefix. This outcome may be unlikely, but it is not impossible for this generator.45:T473,## Pseudo Randomness vs True Randomness A rather serious flaw with the random generation of real numbers as implemented so far is that most programming languages, including JavaScript, use pseudo random number generators to generate random numbers. These generators have a finite cycle of repetition, which means that if the system is run for long enough, it will start to generate the same sequence of random digits again and again. This means that every random number generated in our system using a pseudo random number generator might actually be a rational number with a very long repeating pattern. However, it is also possible to implement a purely mathematical function for generating random numbers that never repeat. This can be done by using the successive digits of an irrational number that is known to be computable, such as the examples given at the beginning of this post. Nevertheless, using this approach would mean that all numbers generated using this random number generator would be a function of a single irrational number, which could potentially limit the range of possible random numbers that can be generated.46:T401,Despite the practical challenges involved in defining an algorithm for generating truly random numbers, we _could_ just assume that it is possible in our mathematical model to choose a sequence of random digits purely randomly. This assumption is related to the "axiom of choice", which states that we can create a new set by choosing one member from each of an infinite number of sets, given a function for making these choices. But we can't rely on the axiom of choice because it only says that we can choose one member from each set, but it doesn't say how to make that choice. So it seems we would need an "axiom of randomness" that assumes it is possible to make a truly random choice. However, it would be simpler if we did not have to just assume a truly random choice is possible. So this question of how to generate a truly random number as a random sequence of digits is not completely resolved, at least if we are only generating the random sequence of digits for _one_ number independent of all other numbers. 47:T480,### True Randomness can be Computed Some people believe that it is impossible to define a truly random number generator computationally. This is not necessarily because the generator is deterministic, meaning that it will always produce the same sequence of numbers given the same starting conditions. The question of whether a random number generator is "pure" or "true" is more about whether the sequence is predictable given any random starting condition. One approach to generating random numbers is to use the digits of an irrational number. This may seem like a good idea because the digits of irrational numbers are typically unpredictable. However, it is conceivable that we might determine which irrational number was used, and thus predict the sequence of random numbers that will be generated. To make the generation of random numbers more unpredictable, we can use not just one irrational number, but a large number of them. If we use an ever-increasing number of irrational numbers in the computation of random numbers, we may be able to generate a sequence of numbers that cannot be predicted unless the same computation is repeated. 48:T4fb,#### Increasingly Unpredictable Random Numbers One way to generate random numbers that are _effectively_ truly random is to use the generation of real numbers itself as the source of randomness. For each digit that we want to choose randomly, we can pseudo-randomly select one of the previously created numbers and use its last added digit. We can then complement this digit ('0' to '1' and '1' to '0') to create a new random digit. While this process depends on a pseudo-random choice of one of the previously created numbers, the fact that we are constantly creating more numbers to choose from means that the repetition in the pseudo-random number sequence will eventually have no discernable impact on the chosen digit. Using this method, we can generate random digits that are effectively truly random. The process begins with a pseudo-random number generator, but as we create more and more numbers, the influence of the pseudo-random generator on the choice of random digits decreases, and the randomness increases. In order to predict the next random digit, one would have to reproduce the entire computation of all digits of all numbers. This means that the randomness of the generated digits approaches true randomness as the number of generated digits increases.49:T1fc2, 4a:[{"id":"da6e3ca1eb5cc32cd902d46943747d05af93597cabf4ba60666eb2d850d175138ae2e5cb186ecb54654bd049a3418cf4d95f1d8aa9180bb9c7e47e4e1a5c1ed6","href":"https://static.observableusercontent.com/files/da6e3ca1eb5cc32cd902d46943747d05af93597cabf4ba60666eb2d850d175138ae2e5cb186ecb54654bd049a3418cf4d95f1d8aa9180bb9c7e47e4e1a5c1ed6","name":"randomX.png","type":"image/png","lastModified":1642465975183.855,"size":195667}] 32:{"id":"b6026de4309eebc3","slug":"computable-real-numbers","title":"Computable Real Numbers","thumbnail":"ca6208fbaddbdfb1062c38fe0e31e90d090f72dd1a1deca2c35ccce185ba9258","access_level":"public","create_time":"$D2022-01-11T23:39:14.361Z","update_time":"$D2022-12-17T02:30:47.009Z","view_time":null,"first_public_time":"$D2022-10-23T23:29:23.444Z","has_unpublished_edits":null,"fork":{"id":"662080314eb2cb2c","slug":"blog-post","title":"Blog Post","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"stars":0,"starred":false,"owner":{"type":"team","id":"8c6e897cb98524c6","login":"real-numbers","name":"Real Numbers","avatar_url":"https://avatars-next.observableusercontent.com/6ce048773a5e4d65a13e5d9d10084f4537d2b2f60df836420dfacd750b8275fa","tier":"starter_2024"},"version":1491,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"b887ef310da1b17a","login":"dlaliberte","name":"Daniel LaLiberte","avatar_url":"https://avatars-next.observableusercontent.com/e5ca1f0f640d7d3579ea69f7316220ebcec267322399e2773f31b91bc2790b15","tier":null}],"members":[{"type":"individual","id":"b887ef310da1b17a","login":"dlaliberte","name":"Daniel LaLiberte","avatar_url":"https://avatars-next.observableusercontent.com/e5ca1f0f640d7d3579ea69f7316220ebcec267322399e2773f31b91bc2790b15","tier":null,"role":"editor"},{"type":"team","id":"8c6e897cb98524c6","login":"real-numbers","name":"Real Numbers","avatar_url":"https://avatars-next.observableusercontent.com/6ce048773a5e4d65a13e5d9d10084f4537d2b2f60df836420dfacd750b8275fa","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Computable Real Numbers","cells":[{"id":0,"value":"# Computable Real Numbers\n\n\n---\n\n---\n\n---\n\n---\n\n---\n\nMoved to https://observablehq.com/@dlaliberte/computable-real-numbers. Please use that link instead of this document. \n\n---\n\n(I was experimenting with whether it might help to use a group (the Real Numbers group) to edit privately, but it did not.)\n\n---\n\n---\n\n---\n\n---\n\n---\n\n---\n\n---\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"// FileAttachment(\"randomX.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":644,"value":"## Abstract\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":435,"value":"// toc(\"h2, h3, h4, h5, h6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":69,"value":"## Precisely Defined Real Numbers\n\nAlthough the full precision of irrational numbers cannot be represented in a rational number system, we can create number objects with precise known values in the sense that we can generate as many digits of the number as needed. In other words, we can generate number objects that effectively have a precise value. This is possible for all Rational numbers, as we showed in \"[Number Objects: Examples](https://observablehq.com/@dlaliberte/number-objects#Examples)\", and it can also be done for irrational numbers as long as we have a program that can generate their digits, as we demonstrate next.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":622,"value":"### The Champernowne Constant\n\nFor example, the `generateChampernowneNumber` function generates a version of the \"[Champernowne Constant](https://mathworld.wolfram.com/ChampernowneConstant.html)\", which simply appends substrings of digits that are the successive counting numbers. Here we represent the counting numbers in binary (i.e. `['1', '10', '11', '100', ...]`). The resulting number is an irrational number because there is no ratio of two (finite) natural numbers that represents its value exactly. But this irrational number is also easily computed using a very simple pattern.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":230,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"value":"champNumbers = generateChampernowneNumber(champernowneOptions.depth)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":626,"value":"In the following visualization and enumeration table, you can see how the Champernowne number is created. As each subsequent digit of the Champernowne number is added, another Real number is also generated that starts with the same prefix but extends it with the opposite last digit.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":233,"value":"viewof champernowneOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"vlembed(\n makeTreeVegaSpec(champNumbers.tree, {\n title: \"Binary Champernowne Constant\",\n width: 600 + champernowneOptions.depth * 5,\n height: Math.max(300, 30 + champernowneOptions.depth * 17)\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"showEnumerationTable(champNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1037,"value":"//viewof db = Debug()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":482,"value":"### The Copeland–Erdős Constant\n\nAnother very similar example is the \"[Copeland–Erdős Constant](https://en.wikipedia.org/wiki/Copeland%E2%80%93Erd%C5%91s_constant)\" which uses the sequence of primes in place of all natural numbers. Although the pattern of this number is still very simple, the use of prime numbers makes this number more interesting because we have no easy way of directly generating the nth prime other than by, effectively, iterating through natural numbers while checking if each one is prime. Here we just use a hard-coded list of the first 95 prime numbers.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":463,"value":"primes = [\n 2,\n 3,\n 5,\n 7,\n 11,\n 13,\n 17,\n 19,\n 23,\n 29,\n 31,\n 37,\n 41,\n 43,\n 47,\n 53,\n 59,\n 61,\n 67,\n 71,\n 73,\n 79,\n 83,\n 89,\n 97,\n 101,\n 103,\n 107,\n 109,\n 113,\n 127,\n 131,\n 137,\n 139,\n 149,\n 151,\n 157,\n 163,\n 167,\n 173,\n 179,\n 181,\n 191,\n 193,\n 197,\n 199,\n 211,\n 223,\n 227,\n 229,\n 233,\n 239,\n 241,\n 251,\n 257,\n 263,\n 269,\n 271,\n 277,\n 281,\n 283,\n 293,\n 307,\n 311,\n 313,\n 317,\n 331,\n 337,\n 347,\n 349,\n 353,\n 359,\n 367,\n 373,\n 379,\n 383,\n 389,\n 397,\n 401,\n 409,\n 419,\n 421,\n 431,\n 433,\n 439,\n 443,\n 449,\n 457,\n 461,\n 463,\n 467,\n 479,\n 487,\n 491,\n 499\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":450,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"copelandErdosNumbers = generateCopelandErdosNumber(copelandErdosOptions.depth)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":454,"value":"viewof copelandErdosOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":469,"value":"vlembed(\n makeTreeVegaSpec(copelandErdosNumbers.tree, {\n title: \"Binary Copeland–Erdős Constant\",\n width: 600 + copelandErdosOptions.depth * 5,\n height: Math.max(300, 30 + copelandErdosOptions.depth * 25),\n linkShape: \"orthogonal\"\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":474,"value":"showEnumerationTable(copelandErdosNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":607,"value":"### The Liouville Number\n\nAnother interesting irrational number is the binary [Liouville Number](https://en.wikipedia.org/wiki/Liouville_number), in which every digit is a '0' except for the '1' digits in the `n!` positions (1, 2, 6, 24, 120, ...) for all natural numbers, `n`. So it will be:\n\n`0.11000100000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001...`\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":572,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":578,"value":"liouvilleNumbers = generateLiouvilleNumber(liouvilleOptions.depth)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":580,"value":"viewof liouvilleOptions = form(html`\n`)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":584,"value":"\nvlembed(\n makeTreeVegaSpec(liouvilleNumbers.tree, {\n title: \"Liouville Numbers\",\n width: Math.max(600, liouvilleOptions.depth * 5),\n height: Math.max(300, 30 + liouvilleOptions.depth * 6)\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":587,"value":"showEnumerationTable(liouvilleNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":703,"value":"### Approximations of the Golden Ratio\n\nAs a final example, we show how we can generate a very useful irrational number, the golden ratio (also known as phi, approximately 1.6180339887498948) as a sequence of increasingly more accurate rational approximations. Each of these approximations is computed as the ratio of a pair of adjacent numbers in the Fibonacci sequence. Since the number object system and visualization are only designed to support numbers between 0 and 1, we will instead approximate the reciprocal of the golden ratio, which in binary is:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":731,"value":"(1 / 1.6180339887498948).toString(2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":699,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":711,"value":"oneOverPhiNumbers = generateOneOverPhi(oneOverPhiOptions.depth)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":713,"value":"viewof oneOverPhiOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":717,"value":"vlembed(\n makeTreeVegaSpec(oneOverPhiNumbers.tree, {\n title: \"Approximations of the Golden Ratio\",\n width: 600 + oneOverPhiOptions.depth * 5,\n height: Math.max(300, 30 + oneOverPhiOptions.depth * 17)\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":992,"value":"In the enumeration table below, you can see that every number is a rational number, `[0, 1, 1/2, 2/3, 3/5, 5/8, 8/13, 13/21, ...]`","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":721,"value":"showEnumerationTable(oneOverPhiNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"$39","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1279,"value":"On the other hand, we know very little about most of these uncomputable numbers because almost every number that we _do_ know about has a rigorous definition that allows us to compute it. In other cases, we do not know whether we can compute a number given its definition, which means that it is _potentially_ uncomputable.\n\nA great summary of our understanding of all the real numbers is presented by Matt Parker in \"[All the Numbers - Numberphile](https://www.youtube.com/watch?v=5TkIe60y2GI)\".\n\nTherefore, the problem we face is how to compute as many digits as requested of _any_ real number, especially any irrational number, using functions over previously known numbers. Given our current understanding of real numbers and functions, this problem appears to be insurmountable. Furthermore, the belief that most real numbers are uncomputable adds to the impression that the task is impossible.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1427,"value":"### Do we Know of any Uncomputable Numbers?\n\nBut we should look a little more closely at these supposedly uncomputable numbers. It appears that the known uncomputable numbers, such as the collection of [Chaitin's constant](https://en.wikipedia.org/wiki/Chaitin%27s_constant) numbers, are considered uncomputable only because they are defined in terms of functions that are uncomputable. \n\nMore specifically, a Chaitin constant \"informally speaking, represents the _probability_ that a randomly constructed program will halt\" [from the wikipedia page]. And since the halting problem cannot be solved, that seems to imply that any of these numbers based on the probability that the corresponding program would halt, are themselves uncomputable. Although there is a specific number that corresponds to such a probability, and Chaitin's function is defined in terms of computing this probability number, it cannot do so because that would require solving the halting problem. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":333,"value":"$3a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":369,"value":"$3b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":403,"value":"$3c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":339,"value":"## One Simple Function that Computes Any Single Real Number\n\nIt turns out that we can use a simple function to generate any combination of digits and therefore generate any single real number. Moreover, we can do this without needing to understand how a sequence of increasingly more complex functions might ultimately allow us to compute these same real numbers.\n\n**The simple function we can use to compute all the digits of any single real number is a random number generator.** \n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1285,"value":"\nThe key point to understand is that each real number can be defined by its infinite sequence of digits, and we can generate as many of these digits as needed for a single random real number using a function that chooses digits randomly, just as well as with any other algorithm.\n\nThis means that any single real number can be made computable by representing it with an object that has a function that can generate any number of the remaining digits of the number randomly. This process aligns closely with the definition of \"[computable numbers](https://en.wikipedia.org/wiki/Computable_number)\", which are \"the real numbers that can be computed to within any desired precision by a finite, terminating algorithm.\"\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":358,"value":"$3d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":141,"value":"$3e","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1121,"value":"mutable nRandomDigits = []","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1124,"value":"function generateNRandomDigits(n) {\n // Slice off extras\n if (nRandomDigits.length > n) {\n nRandomDigits.splice(n);\n }\n // Push on new digits.\n while (nRandomDigits.length < n) {\n nRandomDigits.push(Math.random() < 0.5 ? \"0\" : \"1\");\n // db(\"nd\", nRandomDigits);\n }\n return nRandomDigits;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"depthFirstRandomNumber = generateOneRandomNumberDepthFirst(\n 0 + depthFirstOptions.depth,\n depthFirstOptions.pregenerateX,\n false\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"html`\n${button({\n value: \"Regenerate\",\n divStyle: {\n display: \"inline-block\"\n },\n buttonStyle: {\n background: \"#CCE9FF\"\n },\n titleStyle: {\n \"text-align\": \"center\"\n },\n onclick: ({ button }) => {\n mutable nRandomDigits = [];\n }\n})}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"viewof depthFirstOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"vlembed(\n makeTreeVegaSpec(depthFirstRandomNumber.tree, {\n title:\n \"Depth-first Generation\" +\n (depthFirstOptions.pregenerateX ? \" of Random X \" : \" Without X\"),\n width: 600 + depthFirstOptions.depth * 5,\n height: Math.max(300, 30 + depthFirstOptions.depth * 12),\n hideLabels: depthFirstOptions.depth > 60,\n linkShape: \"diagonal\" // depthFirstOptions.linkShape\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1167,"value":"If you uncheck the \"Pregenerate X\" option, then we don't generate a single 'X' number. Instead, we generate a sequence of new numbers. For each new number, it starts with a subset of the same sequence of random digits used for the X path, but we add the complement of each subsequent digit so that each number branches _away_ from the X path. We label these numbers with `Xi` for each index `i`.\n\nInterestingly, the visualization looks almost the same as for the \"Pregenerate X\" process. The difference is that with a pregenerated X, the color of the path taken by the generation of all digits of X stays the same, whereas without the pregenerated X, the color changes at every step since a new color is used for each new number object that is created at each step. Compare this with the enumeration of Approximations of the Golden Ratio above in which each number in the enumeration is a rational approximation of the golden ratio.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":241,"value":"Notice that in the enumeration table below, when you deselect the \"Pregenerate X\" option, we always see the diagonal digit of every number, and with the \"Pregenerate X\" option we _almost_ see the diagonal digit of every number. This is also the case in all the previous examples shown above. This happens because, in all these cases, by generating numbers depth-first around one number, we will never get around to expanding the rest of the binary tree. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":239,"value":"showEnumerationTable(depthFirstRandomNumber)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":977,"value":"$40","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":395,"value":"$41","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1241,"value":"\n","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":902,"value":"\nThis question of the probability of generating any specific rational or irrational number may ultimately force us to address the connection between the real numbers and the hyperreal numbers, which augment the real numbers with infinitesimal numbers and infinite numbers. When we say the probability of generating a specific number _approaches_ 0, we really mean the probability is infinitesimally small, not that it is _actually_ 0. We have this ongoing confusion in mathematics between the concepts of an infinite sequence that _approaches_ a number and how we leap over the final infinitesimal gap to reach a number at the limit of the sequence, assuming the sequence converges.\n\nWe will have more to say about this subject in subsequent posts.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":538,"value":"$42","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":855,"value":"## Enumeration of N Random Real Numbers\n\nDespite the possibility of collisions identified previously, in this example, we show how to generate not just one random number but any number of them. In order to create each number, the system first tries to find a unique prefix by randomly adding more digits to the number until a new leaf node can be created, and in doing so, it might add digits to a previously generated number that has the same prefix as the new random number. \n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":849,"value":"$43","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":859,"value":"NRandomNumbers = (nRandomNumbersOptions,\ngenerateNRandomNumbers(\n 0 + nRandomNumbersOptions.depth,\n 0 + nRandomNumbersOptions.numNumbers\n))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":862,"value":"viewof nRandomNumbersOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":876,"value":"vlembed(\n makeTreeVegaSpec(NRandomNumbers.tree, {\n title: `Depth-first Generation of ${nRandomNumbersOptions.numNumbers} Random Numbers`,\n width: 600 + nRandomNumbersOptions.depth * 5,\n height: Math.max(300, 30 + nRandomNumbersOptions.numNumbers * 12),\n hideLabels: nRandomNumbersOptions.depth > 60,\n linkShape: \"diagonal\" // nRandomNumbersOptions.linkShape\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":884,"value":"showEnumerationTable(NRandomNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":973,"value":"$44","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":389,"value":"$45","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1370,"value":"Another potential flaw to consider is that, even if the random number generator never repeats, the sequence of random digits we generate from it might not be equally likely. There could be subtle, aperiodic patterns that are not easily detected, or biases in the total number of each digit, or the total number of each unique substring of k adjacent digits. No matter how hard we try to ensure that a non-repeating sequence of digits is as uniformly random as possible, it may still not be random enough to generate every possible sequence of digits. \n\nFortunately, the way we use the random number generator, we do not require a purely _uniform_ probability of generating any possible sequence of digits. We only require that there is a non-zero probability of generating _every possible_ sequence of digits. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1376,"value":"To claim that _any_ single real number can be generated using a sequence of random digits, it appears we must use a \"true\" random number generator that has a non-zero probability of generating any possible sequence of digits. While a physical random number generator based on radioactive decay or a quantum state may be able to provide this level of true randomness, it ultimately relies on the underlying reality of physics, which goes beyond pure mathematics. Thus, we must consider the limits of what can be achieved with pure mathematical concepts alone.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1363,"value":"$46","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1181,"value":"$47","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1386,"value":"\nHowever, even if we can create a random number generator that is completely unpredictable, we still need to consider whether it is capable of generating any possible sequence of random digits. This is our ultimate goal, after all. It doesn't matter how unpredictable the random number generator is if it can't generate every possible combination of random digits. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1391,"value":"$48","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1396,"value":"The pseudo-random number generator used in this process must be minimally random to avoid degenerate cases. An example of a degenerate case would be if the pseudo random number generator always picked the same number; in that case, all digits generated would be the same. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1399,"value":"\nBy the way, we choose the complement of the last digit of the randomly chosen number instead of the digit itself to avoid creating an imbalance in the total quantity of each kind of digit in our random numbers. This way, the probability of always choosing one digit or the other will not increase without end. If we did not complement the chosen digit, for example, and all available choices of digits happened to be the same, we would continue to generate the same digits thereafter.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1404,"value":"While it should be noted that this random number generator will grow without bound as it stores all the digits of all the numbers created, it is nevertheless true that, at every step along the way, only a finite amount of storage is required. This finite storage constraint is essential if we want to comply with the definition of a computable number that requires us to provide a finite length function to compute as many digits as requested. The generator function for digits of random numbers together with this ever-growing but always finite storage of all numbers previously generated meets this requirement.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1157,"value":"To use this system of generating random numbers in a deterministic way, we would need to use a deterministic pseudo random number generator and preserve the exact order of creating and adding every digit. This means that we would either have to centralize the generation of all numbers, or record the order of creation of all digits of all numbers so the process can be repeated exactly. If we want to allow a deterministic pseudo-random number generator to not be limited to a finite number of possibilities, then it would need to accept a starting \"seed\" that is any natural number.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1294,"value":"$49","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1457,"value":"## Follow up Notebooks\n\nThis notebook, on computable numbers raised several more topics that we should followed up on.\n\n1. An enumeration of algebraic numbers would be interesting to see.\n2. A generator of true randomness, as outlined here, could be implemented.\n1. [Countably Infinite Random Real Numbers](https://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers) enumerates all Reals by avoiding the gaps and collisions that could arise in the [Enumeration of N Random Real Numbers](https://observablehq.com/@real-numbers/computable-real-numbers#cell-855) described in this notebook.\n4. The problem with self-referential contradictory definitions will be elaborated upon.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":97,"value":"vlembed = require(\"vega-embed\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"import {\n Real,\n Rational,\n Zero,\n One,\n BinaryTreeNode,\n makeTreeVegaSpec,\n showEnumerationTable,\n ratio\n} from \"@dlaliberte/number-objects\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"import { toc } from \"@nebrius/indented-toc\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":117,"value":"import { form } from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1129,"value":"import { button } from \"@bartok32/diy-inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":786,"value":"import { Debug } from \"@trebor/debug-tool\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":868,"value":"// viewof db = Debug()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4a","stdlib":"1","titling":"auto"}} 33:"$32:body"