|
|
|
|
|
|
by jerf
111 days ago
|
|
|
You can also get to computable numbers through a similar argument, substituting something Turing-complete for algebra. You definitely do get to learn some interesting things about numbers from computable numbers. 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.)