Re: Earliest example of an incomputable real

From: KRamsay (kramsay_at_aol.com)
Date: 06/21/04 

Date: 21 Jun 2004 04:40:43 GMT

In article <3f46af44.0406200820.97b2fd4@posting.google.com>,
contactgreg@hotmail.com (Gregory Magarshak) writes:
|> It was clear that the inequalities you wrote were not exactly
|> the relevant ones; not knowing exactly what argument you had in
|> mind I couldn't guess exactly what the relevant inequalities
|> were, so in my reply the inequalities were also off.
|
|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.

|For example, if your number was 1, as in your example, you
|would check the range 0.99 to 1.00 as opposed to the range 0.95 to
|0.05, as you do.

Generally, though, we won't know that the number is exactly 1. We
may only know that it's somewhere close to 1, which leaves us
without enough information necessarily to follow your instructions.
You say to "check below the number" r. Okay, is 1 below r or not?
The interval (r-0.01,r) can't be "checked" to see whether 1 is in
it until we know whether 1<r.

If 1<r<2, then we must use 1 as the digit before the decimal. If
0<r<1 then we must use 1 as the digit before the decimal. However
we pick the digit, we need to be able to rule out at least one of
the cases r<1 or r>1. If r<1, then we can eventually show that r<1
by computing a close enough approximation to r. If r>1, then we can
eventually show that r>1 by computing a close approximation to r.
But if r=1, then we may never know that r=1, and we may never
be able to rule out r>1 or r<1. We may remain permanently unsure
whether r>1, r<1, or r=1, which leaves us stuck.

To show that r has a computable decimal expansion, you need a
nonconstructive argument, like the one David Ullrich described
earlier in the thread. A nonconstructive argument proving that there
exists an algorithm that computes the n-th digit doesn't have to
give us a way to compute the n-th digit. There's a simple approach
to computing the decimal expansion of r that works as long as we
don't get permanently stuck on one of the digits of r because of this
problem that r might be equal to a terminating decimal without our
knowing it. On the other hand, if r has a terminating decimal
expansion, then the expansion is computable, even if we don't know
what it is. There is no general procedure for determining whether a
computable real has a terminating decimal expansion. But if you do
either find what terminating decimal expansion it has, or show that
it doesn't have one, then you can write down an algorithm.

|Thus, you will discover the decimal expansion of the
|number. The same for negative numbers, but you have to look at the
|range of numbers ABOVE your number. For zero, you don't know whether
|to look above and below, and hence the "funny thing" happens. Perhaps
|zero as a special case can be shown to be computable as in (i) by
|another method.

The decimal expansion of zero is computable for a much simpler
reason; it's just 0.

Keith Ramsay

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: .9 repeating
    ... denote the decimal expansion of x. ... map interpreting digit strings as elements of R'. ... interpretation of decimal notations. ...
    (sci.math)
  • 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 ... Then the k'th digit can be extracted ...
    (sci.math)
  • Re: Paper & pencil password algorithm
    ... Computing something like mul, C) would be twice as much ... Testing if a digit is multiple of three is easy to remember. ... Look at the first empty slot from the left, ... *addKey: Add the key digitwise to the last row. ...
    (sci.crypt)
  • Re: Earliest example of an incomputable real
    ... Turing machine that outputs a decimal expansion of x correct to n ... the machine will finish computing the first k digits in a finite time. ... Are you allowed this arithmetical operation on the reals? ...
    (sci.math)
Loading