Re: Comparing two notions of computable number

From: Toby Ord (toby.ord_at_removethis.philosophy.oxford.ac.uk)
Date: 02/28/04 

Date: Sat, 28 Feb 2004 15:19:53 +0000 (UTC)

In <c1o9o7$p8r$1@uwm.edu> Dr. Yongge Wang wrote:
> 1 and 2 are certainlyh not equivalent. One is related to constructive
> numbers and one is related to approximable numbers...
>
> More information could be found in many places... for example,
> some of my papers and my PhD thesis.
> check it out at: http://www.sis.uncc.edu/~yonwang/papers.html
> or http://www.sis.uncc.edu/~yonwang/research/pastResearch.html

This seems wrong to me. Am I missing some subtlety in what you or Axel
are saying? I thought these definitions were well known to be equivalent
formulations of the recursive reals. Could you name a real that falls
under exactly one definition? Given that a number r is rational, it is
easy to show that the definitions are equivalent and given that it is
irrational seems easy to show as well. These two styles of definition
may come apart from each other if we used a different type of machine or
the like, but here they seem equivalent.

Could you explain or give a more precise reference. I have had a brief
look through your thesis, but found no mention of this distinction.

Toby.

>
> Axel Boldt <axelboldt@yahoo.com> wrote:
>: In http://wikipedia.org/wiki/Computable_number two notions of
>: computable number are given:
>
>: 1) a real number a is computable iff there exists a Turing machine
>: which for given rational number eps produces a rational approximation
>: r such that |a-r|<eps
>
>: 2) a real number a is computable iff there exists a Turing machine
>: which for given natural number n produces the n-th decimal digit of a
>
>: Definition 2 seems to be (equivalent to) Turing's original definition.
>: Clearly, every 2-computable number is 1-computable. Is the converse
>: also true?
>
>: Thanks,
>: Axel
>
>

Relevant Pages

  • Re: Comparing two notions of computable number
    ... perhaps there is a little confusion in your the original definition. ... the approximation or the real r or not. ... the halting probability of a University Turing Machine (or you call ... formulations of the recursive reals. ...
    (comp.theory)
  • Re: Cantors Diagonal Argument
    ... Because for any mapping of N to the interval [0,1) I can ... As far as I can tell, the number of states in the Turing machine ... > without AC we can only generate computable Reals which ...
    (sci.logic)
  • Re: Complex Specified Information - Pitman Formula
    ... I'm sorry, but a Turing machine can't compute pi, it computes ... Since the decimal expansion of pi is ... can't be represented in terms of a finite-sized computer program. ... reals, are the real numbers that can be computed to within any desired ...
    (talk.origins)
  • Re: Kind of NOT integer constant
    ... > I believe that is the definition of "addition" for reals, ... > result of any operation giving a real includes an approximation. ... computational result could differ from the mathematical one. ... Is the compiler that uses extra precision for arithmetic ...
    (comp.lang.fortran)
  • Re: Orthonormalization of function space
    ... reals over the reals, given the inner product: ... Using my inner product routines and after some other checks, ... While this polynomial looks a bit like sin, it is an approximation ... def avg: ...
    (sci.math)