| > The differences between the computables and the full reals are much more subtle than the differences between the rationals and the reals. How so? Using the definition of computable numbers where you provide input of n and the output is every digit of the number up to n places past the decimal point, we can rephrase that definition like so: A computable number c is one with the following property: A Turing machine exists which, provided with a tolerance δ, will exhibit a rational number q < c such that c - q < δ Clearly, a suitable rational will always exist, since rationals can be found within any distance of any real. But for some particular real, we might not be able to find that rational through the use of a fixed Turing machine, in which case the real would be noncomputable. This suggests to me that there is a wider gap between the computables and the reals, where the approximation of a real number is limited by the need to describe it with a Turing machine, than there is between the rationals and the reals, where we can use the same approximation, but without that limitation. (Obviously the rationals are a subset of the computables, but if we're considering a relationship to the real numbers, the rationals seem to have one that is closer and more direct...? The relationship of a computable number to a real number is defined through intermediary rational numbers.) |
I didn't say "wider". I said more subtle. It doesn't take much mathematical intuition and training to understand the rationals versus the reals. Understanding the computables versus the reals is a lot more tricky and takes a lot more thought. The simple arguments that show the difference between the rationals and the reals require a lot of very careful adjustment if you want to translate them to the computables versus the reals.
I agree the gap up to the reals is still bigger than rational -> computable. The reals are weird. This is a meme but there's a lot of truth in it: https://www.reddit.com/media?url=https%3A%2F%2Fpreview.redd....