> 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
is indistinguishable form magic (but not actual magic) and all that
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,
P( X is uncomputable)
should be equal to
P(X is uncomputable within resources I)
since there is no evidence comprehensible by M that can distinguish A
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
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
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
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
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?