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 nonexistence
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?

 is induction unformalizable? Wei Dai
 RE: is induction unformalizable? Ben Goertzel
 RE: is induction unformalizable? Ben Goertzel
 Re: is induction unformalizable? Wei Dai
 RE: is induction unformalizable? Ben Goertzel
 Re: is induction unformalizab... scerir
 Re: is induction unformal... Bruno Marchal
 RE: is induction unformalizable? "Hal Finney"
 Re: is induction unformalizable? Bruno Marchal
 Re: is induction unformalizable? "Hal Finney"
 Re: is induction unformalizable? Wei Dai