Re: Earliest example of an incomputable real

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 06/21/04 

Date: Mon, 21 Jun 2004 16:27:06 -0500

On 21 Jun 2004 09:12:51 -0700, contactgreg@hotmail.com (Gregory
Magarshak) wrote:

>> |No, I am saying that all nonzero numbers satisfying (ii) satisfy (i),
>> |because you check BELOW the number (not on both sides of it) to find
>> |the digits.
>>
>> What you're describing doesn't provide an effective procedure for
>> generating the decimal expansion, so some other method is needed
>> to show that it's computable.
>
>Of course it proves an effective procedure. Maybe it is I who doesn't
>understand what you are talking about, but I think you misunderstand
>me.
>
>Check this out: pick any real number x. Suppose (ii) is true, that is,
>there is a Turing machine or whatever that, given eps, outputs an
>approximation y to x that is within epsilon. Perhaps it gives you a
>rational number; I don't know.
>
>Now you want to show (i), or equivalently, that for every n there is a
>Turing machine that outputs a decimal expansion of x correct to n
>decimal places.

This is _not_ (i). (i) says there is a TM which takes n as an input
and outputs an expansion of x correct to n places. There's a big
difference (although I suspect that you just didn't say what you
meant).

>Suppose that x is strictly positive. Then to discover
>the k'th digit after the decimal point, you would feed the number x -
>6/10^k to the machine

You can't feed the number x - 6/10^k to the machine; it takes
an integer n as input. But that's not important; if we have
a TM giving a sequence of rational approximations to x, with
error bounds, then we can easily construct another TM which
gives rational approximations to x - 6/10^k.

>and set eps to 5/10^k, say. Thus, the machine
>will output a number y in the range
>x - 11/10^k < y < x - 1/10^k
>as opposed to in the range
>x - 5/10^k < y < x + 5/10^k
>as it would using David's method. Then the k'th digit can be extracted
>from y.

Nope. Knowing that y is in such a range simply does not tell
you what the k-th digit of x is. (Ok then, explain very carefully
and very completely exactly how it does. Make certain not to
miss any special cases, because you _can_ do this "most" of
the time...)

************************

David C. Ullrich

Relevant Pages

  • Penroses Computing Pi Description?
    ... of a Turing machine can, strictly speaking, be an infinite ... I realize that computing infinity does not come to ... If we wish to generate an infinite decimal expansion, ... then the second decimal digit, 4, by making it act ...
    (sci.logic)
  • Re: Earliest example of an incomputable real
    ... >> generating the decimal expansion, so some other method is needed ... >Of course it proves an effective procedure. ... >Turing machine that outputs a decimal expansion of x correct to n ... about _any_ of the digits of x. ...
    (sci.math)
  • Re: .9 repeating
    ... denote the decimal expansion of x. ... map interpreting digit strings as elements of R'. ... interpretation of decimal notations. ...
    (sci.math)
  • Re: Arbitrary strings of digits in the decimal display of Pi
    ... Let Fdenote the number of positive integers less than n that do not ... contain digit 5 in their decimal expansion. ... contain digit 5 in their decimal expansions converge? ... What is the sum of the reciprocals of all p-smooth positive integers? ...
    (sci.math.symbolic)
  • Re: 31 bit pseudo-random number gen in C, C++ & dsPIC assembly code
    ... > The random sequence decision question: ... it seems that there is no such Turing machine. ... the random digit generator. ... If not (this happens with probability ...
    (comp.dsp)