RE: is induction unformalizable?

From: Ben Goertzel <ben.domain.name.hidden>
Date: Wed, 13 Jul 2005 23:54:38 -0400

Wei,

I forwarded your post to a few of my colleagues, and one of them (Moshe
Looks) replied with basically the same solution as I already posted here,
but in different words...

Here is his reply...

-- Ben



> Correct me if wrong, but isn't the halting problem only

> undecidable when the length of the program is unbounded? Wouldn't the AI
assign non-zero

> probability to a machine that solved the halting problem for

> programs up to size S? (S is the number of stars in the sky, grains of
sand,

> atoms in the universe, etc...) As an aside, this would actually be my best
guess as to

> what was really going on if I were presented with such a box (and I'm not

> even programmed with UD+ASSA, AFAIK). Any sufficiently advanced

> technology is indistinguishable form magic (but not actual magic) and all
that ;->...

>

> Moshe


  -----Original Message-----
  From: Ben Goertzel [mailto:ben.domain.name.hidden]
  Sent: Wednesday, July 13, 2005 11:35 PM
  To: Wei Dai; everything-list.domain.name.hidden
  Subject: RE: is induction unformalizable?


  Wei,

  Isn't the moral of this story that, to any finite mind with algorithmic
information I, "uncomputable" is effectively synonymous with "uncomputable
within resources I"?

  Thus, from the perspective of a finite mind M,

  A = P( X is uncomputable)

  should be equal to

  B = P(X is uncomputable within resources I)

  since there is no evidence comprehensible by M that can distinguish A from
B.

  Any formalization of induction that says A and B are unequal is not a
correct model of induction as experienced by a finite mind.

  Induction is formalizable, but only using *experience-based semantics*, in
which one assigns probabilities to propositions based on actual experienced
pieces of evidence in favor of these propositions.

  Considering induction outside of the context of a particular finite
system's experience leads to apparent paradoxes like the one you're
suggesting. But if one construes induction experientially, one finds that
these paradoxes never occur in any finite system's experience.

  As an example of experience-based semantics, see Pei Wang's NARS theory of
AI. I don't fully accept the NARS theory, I have my own related theory that
is probabilistically grounded, unlike NARS. But NARS is an example of what
experience-based semantics means in concrete mathematical practice.

  -- Ben

    -----Original Message-----
    From: Wei Dai [mailto:weidai.domain.name.hidden]
    Sent: Wednesday, July 13, 2005 11:15 PM
    To: everything-list.domain.name.hidden
    Subject: is induction unformalizable?


    One day, Earth is contacted by a highly advanced alien civilization, and
they tell us that contrary to what most of us think is likely, not all of
the fundamental physical laws of our universe are computable. Furthermore,
they claim to be able to manufacture black boxes that work as oracles for
the Halting Problem of Turing machines (one query per hour). They give us
one free sample, and want to sell us more at a reasonable price. But of
course we won't be allowed to open up the boxes and look inside to find out
how they work.

    So our best scientists test the sample black box in every way that they
can think of, but can't find any evidence that it isn't exactly what the
aliens claim it is. At this point many people are ready to believe the claim
and spend their hard earned money to buy these devices for their families.
Fortunately, the Artificial Intelligence in charge of protecting Earth from
interstellar fraud refuses to allow this. Having been programmed with
UD+ASSA (see Hal Finney's 7/10/2005 post for a good explanation of what this
means), it proclaims that there is zero probability that Halting Problem
oracles can exist, so it must be pure chance that the sample black box has
correctly answered all the queries submitted to it so far.

    The moral of this story is that our intuitive notion of induction is not
fully captured by the formalization of UD+ASSA. Contrary to UD+ASSA, we will
not actually refuse to believe in the non-existence of uncomputable
phenomena no matter what evidence we see.

    What can we do to repair this flaw? Using a variant of UD, based on a
more powerful type of computer (say an oracle TM instead of a plain TM),
won't help because that just moves the problem up to a higher level of the
computational hierarchy. No matter what type of computer (call it C) we base
UD' on, it will always assign zero probability to the existence of even more
power types of computer (e.g., ones that can solve the halting problem for
C). Intuitively, this doesn't seem like a good feature.

    Earlier on this mailing list, I had proposed that we skip pass the
entire computational hierarchy and jump to the top of the set theoretic
hierarchy, by using a measure that is based a set theoretic notion of
complexity instead of a computational one. In this notion, instead of
defining the complexity of an object by the length of its shortest
algorithmic description, we define its complexity by the length of its
shortest description in the language of a formal set theory. The measure
would be constructed in a manner analogous to UD, with each set theoretic
description of an object contributing n^-l to the measure of the object,
where n is the size of the alphabet of the set theory, and l is the length
of the description. Lets call this STUM for set theoretic universal measure.

    STUM along with ASSA does a much better job of formalizing induction,
but I recently realized that it still isn't perfect. The problem is that it
still assigns zero probability to some objects that we intuitively think is
very unlikely, but not completely impossible. An example would be a device
that can decide the truth value of any set theoretic statement. A universe
that contains such a device would exist in the set theoretic hierarchy, but
would have no finite description in formal set theory, and would be assigned
a measure of 0 by STUM.

    I'm not sure where this line of thought leads. Is induction
unformalizable? Have we just not found the right formalism yet? Or is our
intuition on the subject flawed?
Received on Wed Jul 13 2005 - 23:55:29 PDT