I agree that
"
As S goes to infinity, the AI's probability would converge to 0, whereas the
human's would converge to some positive constant.
"
but this doesn't mean induction is unformalizable, it just means that the
formalization of cognitive-science induction in terms of algorithmic
information theory (rather than experience-grounded semantics) is flawed...
ben
-----Original Message-----
From: Wei Dai [mailto:weidai.domain.name.hidden]
Sent: Thursday, July 14, 2005 1:05 AM
To: Ben Goertzel; everything-list.domain.name.hidden
Subject: Re: is induction unformalizable?
>> 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
The AI would assign approximately 2^-S to this probability. A human being
would intuitively assign a significantly greater a priori probability,
especially for larger values of S. As S goes to infinity, the AI's
probability would converge to 0, whereas the human's would converge to some
positive constant.
Why 2^-S? Being able to solve the halting problem for programs up to size
S is equivalent to knowing the first S bits of the halting probability
(Chaitin's Omega). Since Omega is incompressible by a Turing machine, the
length of the shortest algorithmic description of the first S bits of Omega
is just S (plus a small constant). See
http://www.umcs.maine.edu/~chaitin/xxx.pdf.
Here's another way to see why the AI's method of induction does not
capture our intuitive notion. Supposed we've determined empirically that the
black box can solve the halting problem for programs up to some S. No matter
how large S is, the AI would still only assign a probability of 2^-100 to
the black box being able to solve halting problems for programs of size
S+100.
Received on Thu Jul 14 2005 - 01:31:02 PDT