Re: Comparing two notions of computable number
From: Dr. Yongge Wang (wang_at_cs.uwm.edu)
Date: 02/28/04
- Next message: Piotr Wyderski: "Re: Distance between equations"
- Previous message: David Wagner: "Re: Distance between equations"
- In reply to: Toby Ord: "Re: Comparing two notions of computable number"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 28 Feb 2004 22:25:27 GMT
OK, perhaps there is a little confusion in your the original definition.
The difference is: given a \epsilon, can you effectively find
the approximation or the real r or not. If yes, then of course
the definitions are equivalent. However, from the description
of the definition, I understood it means, for any given \epsilon,
your Turing machine will soon or later produce a a such that
|a-r|<\epsilon.
Then the two definitions are not equivalent.
The classical example is:
the halting probability of a University Turing Machine (or you call
it Chaitin \Omega number) is approximable in this way. But it
it not computable in the sense that you cannot know what is the
n-th bit of this number though you know you will reach it some time.
So again, I may misunderstand the original definition in the
original post. But if you mean the above approximation
then the difference is the same as the Martin-Loef test and
rec-test. That is, the different between Martin-Loef test martingable
and recursive martingale in my thesis.
Regards,
Yongge Wang
Toby Ord <toby.ord@removethis.philosophy.oxford.ac.uk> wrote:
: 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...
: 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
:>
:>
--
- Next message: Piotr Wyderski: "Re: Distance between equations"
- Previous message: David Wagner: "Re: Distance between equations"
- In reply to: Toby Ord: "Re: Comparing two notions of computable number"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
