4 ms·

First and foremost: > The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to

First and foremost: > The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming Actually countability does lend itself to programming, essentially by definition. You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time. You can trivially do this with a "merely" countably infinite set, like the naturals or rationals. > Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0). It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. This fact follows from the field axioms for the same reason that all products of irrationals and rationals are themselves irrational. Simply put, if you can't do it for Pi, you can't do it for a rational multiple of Pi.

mike00632 8y ago
>You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable. You're right that we can't write a function to determine an immediate successor but we can write successor functions. >It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. We are getting a few concepts muddled. Storing an irrational number as a finite representation is trivially easy. For example: "pi". Alternatively I could write an algorithm to generate the decimal expansion of the square root of 2. Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. There is a certain unknowable quality to these numbers and I would suggest that this isn't inherent from the cardinality of the real numbers and that we run into similar problems when trying to compute some natural numbers, like random numbers.
- throwawaymath 8y ago
  > Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable. Huh? You can trivially write a function to generate all natural numbers: def increment(x): return increment(x + 1) increment(1) How do you propose doing that for the reals? > Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. This is not what uncomputable means. Uncomputable means we cannot calculate a number to any precision, not that the number has an infinite decimal expansion. Pi is not uncomputable. You can’t store its entire decimal expansion in finite space but it is certainly computable - we compute it all the time. However, almost all real numbers are strictly uncomputable. Among many other proofs, this is evident from the simple fact that the set of all possible Turing machines is countable. Since the reals are uncountable, it follows that almost all reals must not be computable by any Turing machine. Likewise, there are many potential calculations involving real numbers for which a computer will output a strictly incorrect - not just imprecise - result because its real solution is uncomputable. This does not happen in the naturals or rationals.
  - antidesitter 8y ago
    > Uncomputable means we cannot calculate a number to any precision Did you mean “for any precision, we cannot compute to that precision” or “we cannot compute to every precision”?
- antidesitter 8y ago
  > Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. I might be nitpicking here, but uncomputable != indescribable. For example, Chaitin’s constant [1] is uncomputable but perfectly describable (and in fact limit-computable [2]). The set of arithmetically-definable [3] numbers is even larger than that of limit-computable numbers. Computable and limit-computable numbers lie at levels Δ^0_1 and Δ^0_2 of this hierarchy, respectively. [1] https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant [2] https://en.wikipedia.org/wiki/Computation_in_the_limit https://en.wikipedia.org/wiki/Computation_in_the_limit [3] https://en.wikipedia.org/wiki/Arithmetical_set https://en.wikipedia.org/wiki/Arithmetical_set

mike00632 8y ago

>You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable. You're right that we can't write a function to determine an immediate successor but we can write successor functions. >It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. We are getting a few concepts muddled. Storing an irrational number as a finite representation is trivially easy. For example: "pi". Alternatively I could write an algorithm to generate the decimal expansion of the square root of 2. Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. There is a certain unknowable quality to these numbers and I would suggest that this isn't inherent from the cardinality of the real numbers and that we run into similar problems when trying to compute some natural numbers, like random numbers.

throwawaymath 8y ago
> Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable. Huh? You can trivially write a function to generate all natural numbers: def increment(x): return increment(x + 1) increment(1) How do you propose doing that for the reals? > Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. This is not what uncomputable means. Uncomputable means we cannot calculate a number to any precision, not that the number has an infinite decimal expansion. Pi is not uncomputable. You can’t store its entire decimal expansion in finite space but it is certainly computable - we compute it all the time. However, almost all real numbers are strictly uncomputable. Among many other proofs, this is evident from the simple fact that the set of all possible Turing machines is countable. Since the reals are uncountable, it follows that almost all reals must not be computable by any Turing machine. Likewise, there are many potential calculations involving real numbers for which a computer will output a strictly incorrect - not just imprecise - result because its real solution is uncomputable. This does not happen in the naturals or rationals.
- antidesitter 8y ago
  > Uncomputable means we cannot calculate a number to any precision Did you mean “for any precision, we cannot compute to that precision” or “we cannot compute to every precision”?
antidesitter 8y ago
> Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. I might be nitpicking here, but uncomputable != indescribable. For example, Chaitin’s constant [1] is uncomputable but perfectly describable (and in fact limit-computable [2]). The set of arithmetically-definable [3] numbers is even larger than that of limit-computable numbers. Computable and limit-computable numbers lie at levels Δ^0_1 and Δ^0_2 of this hierarchy, respectively. [1] https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant [2] https://en.wikipedia.org/wiki/Computation_in_the_limit https://en.wikipedia.org/wiki/Computation_in_the_limit [3] https://en.wikipedia.org/wiki/Arithmetical_set https://en.wikipedia.org/wiki/Arithmetical_set