Re: does sqrt(2) exist in CM?

examachine_at_gmail.com
Date: 02/19/05 

Date: 19 Feb 2005 14:36:41 -0800

Keith Ramsay wrote:
> examachine@gmail.com wrote:
> [...]
> |If you claim that I'm merely buying into the PR of AIT, and it's not
> an
> |interesting subject for me, then I think you'd be wrong.
>
> I don't claim that.
>
> My concern was not that you might be buying into p.r. (And
> how would finding the advertised product "interesting" mean
> that you weren't? The most effective p.r. campaigns leave
> people interested.) Generally, I'm not worried that it might
> appeal to you too much in its own terms. It's rather that I
> suspect you may be judging it as more novel in *relative*
> terms, from lack of familiarity with what was already done
> in related areas.
>
> A few postings back, you asked me (out of "curiosity")
> whether there was a "natural hierarchy of computability
> notion for reals", whether such a thing had been worked out.
> And apparently you weren't familiar with the theory of
> Turing degrees. That's one really big area. Of course I can
> only really guess how much you know generally.

I asked this to suggest that any such natural hierarchy should
automatically correspond to a hierarchy of randomness definitions, as a
side point which perhaps remained unilluminated. On the other hand, you
are right that I was not awfully familiar with this "one really big
area" except having read the chapters about oracles in our theory of
computation textbook, which was not taught to us unfortunately. :( As
you talked some ideas re-generated, but no, I had not studied the
Turing degrees of reals in particular.

Perhaps you would like me to know everything, and not ask anything. I
would have liked that, too, which is unlikely for so many of us.

BTW, I haven't yet seen any informative remarks on the hierarchy of
randomness definitions which Chaitin writes about. What does the
"existence" of such a hierarchy mean, in what sense does it exist?
Perhaps, I wonder, in the same sense as certain hierarchies in set
theory?

I am sorry for not being explicit enough. Perhaps this time, the force
of my questions pass through.

> [...]
> | I favor this subject not merely because of
> | the application aspects (AI), but also because of its philosophical
> | import.
>
> Again, I recommend putting what you might read or think in
> this area into broader perspective.

Recommendation taken.

> [...]
> | I like combinatorics and optimization, too, so I should be looking
> | into stability theory better. Can you offer any web resources for
an
> | overview of the main results/concepts?
>
> Your google search is as good as mine. :-) (Sorry.)

Anybody else then? Since I'm not already familiar with the stuff, I
can't distinguish an authoritative reference from that is not. Some
texts, as you know, are the wrong way to start reading on a subject.

> Kreisel remarked once something to the effect that logic
> tends to deal in very broad categories (computable versus
> uncomputable and so on). One thing I like about the theory
> of stable theories is that it makes distinctions on a more
> "human" level that seem to correlate with qualities we
> look for already.

I agree with the general nature of this remark.

It is then, I hope, apparent, how important it may be to cast these
metamathematical and logical questions in the language of an abstract
specification of all programming languages and data structures, rather
than an awkward low level machine specification such as the Turing
machine, or first order logic, or what not.

> It seems like AIT might be capable of descending from the
> clouds and applying to mundane issues more, but it also
> seems to be hard to get it to do so. (I was somewhat
> disappointed when I first saw the Li and Vitanyi book that
> the applications weren't more down-to-earth, but I suppose
> it's partly in the nature of the business for it to be
> hard to apply concepts on that level. Probably I will go
> look at it again someday.)

Yes, it is. Due to my status as a third world country university
student, I have not been able to acquire this book in question.
However, I have read the relevant papers from the web. One of the most
interesting papers I saw, was an elaboration of the information
distance, which shows the mutual information between the forward and
backward transformation programs.

On the other hand, the general concept of algorithmic probability has
opened completely new horizons for AI research. If you are interested
in AI at all, I think you should have a look.

Regards, 

--
Eray

Relevant Pages

  • Re: does sqrt(2) exist in CM?
    ... > whether there was a "natural hierarchy of computability ... I asked this to suggest that any such natural hierarchy should ... Turing degrees of reals in particular. ... Can you offer any web resources for ...
    (sci.logic)
  • Re: does sqrt(2) exist in CM?
    ... > whether there was a "natural hierarchy of computability ... I asked this to suggest that any such natural hierarchy should ... Turing degrees of reals in particular. ... Can you offer any web resources for ...
    (comp.theory)
  • Re: The Macintosh is a girls computer!
    ... (Rowland McDonnell) ... everyone else in the hierarchy thought he was potty on the subject. ... codebooks used by Turing et al recovered from a captured U-Boat? ...
    (uk.comp.sys.mac)
  • Re: What does diagonalization prove?
    ... you take computability as equivalent to existence. ... things exist, the enumeration from integers to Com is uncomputable, ... has an associated Goedel number that is an integer. ... "Kleene hierarchy", of sets. ...
    (sci.math)