3 ms·

Is there a smallest uncomputable number? Or maybe that's not a well-formed question? Simplest uncomputable number? Simplest algorithm which produces uncomputabl

by l0b0 3y ago

Is there a smallest uncomputable number? Or maybe that's not a well-formed question? Simplest uncomputable number? Simplest algorithm which produces uncomputable numbers? Confused now.

justicz 3y ago
I don’t think so, because you could divide any uncomputable number by an arbitrary computable constant and it would still be uncomputable. I think!
- l0b0 3y ago
  Yeah, I updated the comment based on that. I guess you'd have to formulate it very specifically to get an interesting answer.
dchftcs 3y ago
I think this is the wrong question. Any number, if you define them as a representation of digits, is computable in that sense. What isn't necessary computable is the value of a function taken with a certain input or input range. BB numbers, as large as they can be, are themselves finite and therefore "computable" once you know them, but the mapping from natural numbers to BB numbers is not computable. So the real value of a particular function f evaluated at some number say 100 could be as small as 0, but maybe you just can't compute f(100) and know that it's 0.
- teraflop 3y ago
  > Any number, if you define them as a representation of digits, is computable in that sense. You have to be a bit careful, here. What you're saying is true of integers (such as the values taken by the BB function), as well as rationals. But it's not true of real numbers, because the reals are uncountable, and therefore there are infinitely many real numbers that cannot be finitely "described" or written down (in whatever notation you happen to care about). An example of an uncomputable real number: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
howinteresting 3y ago
"Computability" is defined in terms of series and algorithms — it there's an algorithm to generate a series of numbers, the series is (by definition) computable. The Busy Beaver series of numbers stand out because there's no possible algorithm to generate them, per the halting problem. Also due to the halting problem, they grow faster than any possible computable series. In other words, for any series S(n), at some point you're going to hit a k such that for all numbers m greater than or equal to k, BB(m) > S(m). So in that sense a "smallest incomputable number" is not well-defined. However it is reasonable to call them the simplest possible description (not algorithm, just a description) of an incomputable series of numbers. There are more complex descriptions of incomputable numbers, such as the Busy Beaver number defined with respect to a Turing machine that has a busy beaver oracle attached to it.
cvoss 3y ago
To get one's head around the concept of an uncomputable number, you must come at it from the realm of uncomputable functions. I sometimes think of big-O computational complexity as a (finite) analogy for uncomputability. For example, the naive matrix multiplication algorithm for n-by-n matrices is O(n^3). That means there is a cubic function relating the size of the input (in terms of n) to the number of steps required to produce the output. But it's not meaningful to ask "what is the computation complexity of multiplying 100-by-100 matrices?"---the answer to this question is O(1), constant time. I.e., it takes ~1000000 steps, every time! In other words, n^3 is a cubic function, but 100^3 is not a cubic function in any meaningful sense; the function n^3 has a polynomial degree, not the output of the function on a particular input. In the same way, it's not meaningful to ask about the computability of specific known numbers: if you know the number, then you have computed it. Instead, you must ask about numbers which are, themselves, functions. (Not a number that is the output of a function on some input, mind you. I mean a number that is encoded by the entirety of the function, across all possible inputs.) Someone has elsewhere mentioned Chaitin's constant as an example of an uncomputable number. What is meant in this case by "uncomputable number" is that we can only describe the number indirectly, rather than put our hands on it directly: The (say) decimal expansion of the digits (aka a machine that spews them out in order from left to right) as encoded by a function mapping the natural numbers to digits, is an uncomputable function. It was also mentioned elsewhere that the possibility of a number being uncomputable in this sense is special to the real numbers, as opposed to, say, the integers. However, I disagree. An integer can indeed be uncomputable in the same sense. If you have honestly no idea how big the integer in question is, to represent it you need a machine that emits its digits right to left (rather than left to right for decimals as we were imagining above), which is again a function mapping the naturals to digits. Such a function may be uncomputable, which would mean you have no way of determining if and/or when it will begin spitting out only zeros after a certain point (which would provide an upper bound for your integer). If any of this is interesting, you may enjoy the Berry paradox. [0] [0] https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox

by l0b0 3y ago

Is there a smallest uncomputable number? Or maybe that's not a well-formed question? Simplest uncomputable number? Simplest algorithm which produces uncomputable numbers? Confused now.

justicz 3y ago

I don’t think so, because you could divide any uncomputable number by an arbitrary computable constant and it would still be uncomputable. I think!

l0b0 3y ago
Yeah, I updated the comment based on that. I guess you'd have to formulate it very specifically to get an interesting answer.

dchftcs 3y ago

I think this is the wrong question. Any number, if you define them as a representation of digits, is computable in that sense. What isn't necessary computable is the value of a function taken with a certain input or input range. BB numbers, as large as they can be, are themselves finite and therefore "computable" once you know them, but the mapping from natural numbers to BB numbers is not computable. So the real value of a particular function f evaluated at some number say 100 could be as small as 0, but maybe you just can't compute f(100) and know that it's 0.

teraflop 3y ago
> Any number, if you define them as a representation of digits, is computable in that sense. You have to be a bit careful, here. What you're saying is true of integers (such as the values taken by the BB function), as well as rationals. But it's not true of real numbers, because the reals are uncountable, and therefore there are infinitely many real numbers that cannot be finitely "described" or written down (in whatever notation you happen to care about). An example of an uncomputable real number: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant

howinteresting 3y ago

"Computability" is defined in terms of series and algorithms — it there's an algorithm to generate a series of numbers, the series is (by definition) computable. The Busy Beaver series of numbers stand out because there's no possible algorithm to generate them, per the halting problem. Also due to the halting problem, they grow faster than any possible computable series. In other words, for any series S(n), at some point you're going to hit a k such that for all numbers m greater than or equal to k, BB(m) > S(m). So in that sense a "smallest incomputable number" is not well-defined. However it is reasonable to call them the simplest possible description (not algorithm, just a description) of an incomputable series of numbers. There are more complex descriptions of incomputable numbers, such as the Busy Beaver number defined with respect to a Turing machine that has a busy beaver oracle attached to it.

cvoss 3y ago

To get one's head around the concept of an uncomputable number, you must come at it from the realm of uncomputable functions. I sometimes think of big-O computational complexity as a (finite) analogy for uncomputability. For example, the naive matrix multiplication algorithm for n-by-n matrices is O(n^3). That means there is a cubic function relating the size of the input (in terms of n) to the number of steps required to produce the output. But it's not meaningful to ask "what is the computation complexity of multiplying 100-by-100 matrices?"---the answer to this question is O(1), constant time. I.e., it takes ~1000000 steps, every time! In other words, n^3 is a cubic function, but 100^3 is not a cubic function in any meaningful sense; the function n^3 has a polynomial degree, not the output of the function on a particular input. In the same way, it's not meaningful to ask about the computability of specific known numbers: if you know the number, then you have computed it. Instead, you must ask about numbers which are, themselves, functions. (Not a number that is the output of a function on some input, mind you. I mean a number that is encoded by the entirety of the function, across all possible inputs.) Someone has elsewhere mentioned Chaitin's constant as an example of an uncomputable number. What is meant in this case by "uncomputable number" is that we can only describe the number indirectly, rather than put our hands on it directly: The (say) decimal expansion of the digits (aka a machine that spews them out in order from left to right) as encoded by a function mapping the natural numbers to digits, is an uncomputable function. It was also mentioned elsewhere that the possibility of a number being uncomputable in this sense is special to the real numbers, as opposed to, say, the integers. However, I disagree. An integer can indeed be uncomputable in the same sense. If you have honestly no idea how big the integer in question is, to represent it you need a machine that emits its digits right to left (rather than left to right for decimals as we were imagining above), which is again a function mapping the naturals to digits. Such a function may be uncomputable, which would mean you have no way of determining if and/or when it will begin spitting out only zeros after a certain point (which would provide an upper bound for your integer). If any of this is interesting, you may enjoy the Berry paradox. [0] [0] https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox