Menu
AFAIK, turing computable numbers are numbers whose i-th index can be returned by a Turing Machine. So a non-computable number would be something like a number whose decimal points are decided if some other program halts on some other input, etc. But then again, PI is a real number, which cannot be enumerated by a T.M. and thus, cannot be computed? So which school of thought is correct?
658
Since a Turing machine can be programmed to compute π, an accelerating Turing machine can execute each act of writing that is called for by this program before two moments of operating time have elapsed.
A real number is computable if and only if there is a computable Dedekind cut D corresponding to it. The function D is unique for each computable number (although of course two different programs may provide the same function). A complex number is called computable if its real and imaginary parts are computable.
Think clearly about the subject for a few days, and you will see that the computable real numbers are not countable, and are complete.
Turing then showed that these computable numbers could give rise to uncomputable ones—ones that could not be calculated using a definite rule—and that therefore there could be no "mechanical process" for solving all mathematical questions, since an uncomputable number was an example of an unsolvable problem.
Yes, π is computable. There are a few equivalent definitions of computable, but the most useful one here is the one you have given above: a real number r is computable if there exists an algorithm to find its nth digit. Here is such an algorithm.
Your last argument is not sound; you have confused the definition "can find the nth digit" with "can enumerate all the digits". The latter is not a useful definition: it rules out all the irrationals and many rationals as well!
An interesting fact is that the computable numbers are in fact countable, since we may Godel-number the Turing machines which produce them. Hence almost no reals are computable.
111
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
