Re: does sqrt(2) exist in CM?

From: Keith Ramsay (kramsay_at_aol.com)
Date: 02/12/05 

Date: 12 Feb 2005 13:00:14 -0800

examachine@gmail.com wrote:
| Where does a Super-Omega fit in the hierarchy of Turing degree?

I wouldn't assume if I were you that the term "super-omega"
has been used enough to become a standard term of the field.
I looked for awhile without success for a definition that
said explicitly, "A super-omega is...". Schmidhuber appears
however to use it in reference to some limit-computable
reals that he finds interesting.

The Turing degree of computable sets of natural numbers is
denoted by 0. There's an operation known as the "jump", which
for a Turing degree represented by a set X yield the Turing
degree of the set X', where n is a member of X' if the n-th
Turing machine with an oracle to X halts. All limit-computable
reals belong to degrees < 0''. Schmidhuber's reals are between
0' and 0''. (Incidentally, there are lots of degrees between
0 and 0', and between 0' and 0''. Turing degrees are partially
ordered, too.)

There's another hierarchy that is a little more suited to
talking about limit-computable reals. If a predicate P(n)
can be expressed in the form

   (En1)(An2)...(E/An_k) Q(n1,...,nk,n)

where it's (En_k) if k is odd and (An_k) if k is even, and
where Q is a primitive recursive predicate, then P is said
to be sigma-0-k. If the same is true but with the alternating
quantifiers starting with (An1), then it's pi-0-k. If it can
be expressed both as sigma-0-k and as pi-0-k it's called
delta-0-k.

The limit computable reals are those reals where the
predicate "the n-th bit of r is 1" is delta-0-2. They are
also the ones computable by a Turing machine with an oracle
to the halting problem for ordinary Turing machines.

The distinction between Schmidhuber's reals and the Chaitin
Omega has to do with the distinction between being a limit
of a computable sequence of rationals, and being a limit of
a *monotone increasing* sequence of rationals. Schmidhuber
exhibits reals that are limits of computable sequences of
rationals (in a noneffective way of course) but not of a
computable monotone sequence of rationals, which Chaitin's
Omega is.

The pi-0-n/sigma-0-n/delta-0-n hierarchy puts them all into
delta-0-2 (and they are not pi-0-1 or sigma-0-1). Turing
degrees make more refined distinctions but they are
insensitive to such issues as terseness; if X is a set of
natural numbers, the set {2n : n is in X} has the same
Turing degree as X but has been "fluffed up". I don't happen
to know the full details of how the reals that are limits
or monotone increasing limits of computable sequences of
rationals fit into the degrees below 0''.

I'd be a lot more impressed by most of these results in AIT
if they had been proven in the 1940s when Post et al. were
doing degree theory, and somewhat more if they had at least
been proven a generation ago, nearer to when Kolmogorov et
al. were defining Kolmogorov complexity and so on. Now, I
find myself asking myself, "Wasn't this stuff known a long
time ago?" Perhaps it's like a plant that is managing to grow
in a gap left by various older, larger trees on different
sides of it, but I don't know. I suspect it gives the
impression of greater novelty than it has, because it's been
presented as a separate field. The techniques seem relatively
old-fashioned to me.

Keith Ramsay

Relevant Pages

  • Re: does sqrt(2) exist in CM?
    ... computability. ... > for a Turing degree represented by a set X yield the Turing ... > talking about limit-computable reals. ... > of a computable sequence of rationals, ...
    (comp.theory)
  • Re: does sqrt(2) exist in CM?
    ... computability. ... > for a Turing degree represented by a set X yield the Turing ... > talking about limit-computable reals. ... > of a computable sequence of rationals, ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... computability. ... > for a Turing degree represented by a set X yield the Turing ... > talking about limit-computable reals. ... > of a computable sequence of rationals, ...
    (sci.logic)
  • Re: does sqrt(2) exist in CM?
    ... reals that he finds interesting. ... The Turing degree of computable sets of natural numbers is ... a *monotone increasing* sequence of rationals. ...
    (comp.theory)
  • Re: does sqrt(2) exist in CM?
    ... reals that he finds interesting. ... The Turing degree of computable sets of natural numbers is ... a *monotone increasing* sequence of rationals. ...
    (sci.logic)