computation vs definition (was: Kiln People)

From: Wei Dai <weidai.domain.name.hidden>
Date: Tue, 22 Jan 2002 16:48:07 -0800

On Fri, Jan 18, 2002 at 09:22:57PM -0800, hal.domain.name.hidden wrote:
> I'm not convinced about the models of computation involving GTMs and
> such in Juergen Schmidhuber's paper. Basically these kinds of TMs can
> change their mind about the output, and the machine doesn't know when
> it is through changing its mind. So there is never any time you can
> point to the output or even a prefix and say that part is done. It is
> questionable to me whether this ought to count as computation. I will
> write some more about his paper tomorrow, I hope.

I'm no longer sure that computation is a necessary ingredient. Why assume
that a universe must be computable (by whatever definition of computation)
in order for it to exist?

To me, the attraction of GTM was that it let's you define a more dominant
prior, so that you don't have to rule out (i.e. not care about) universes
with things like halting oracles a priori. However I now realize that even
the GTM-based prior is still not dominant enough, because it rules out
things like convergence oracles (i.e. an oracle that tells you whether the
output of a GTM will converge).

I think we need an even more dominant prior and associated notion of
complexity, based on a concept of definitional description rather than
computational description. Maybe it can be based on second-order logic. I
just finished reading Steward Shapiro's _Philosophy of Mathematics :
Structure and Ontology_, where he argues that all mathematical strucutures
that can be defined by second-order theories exist. (This seems very
similar to Max Tegmark's position, but more clearly defined.) I'm going to
read his _Foundations Without Foundationalism : A Case for Second-Order
Logic_ to learn more about second-order logic and see if it's possible to
obtain a definition of complexity and a measure from it.

> I wonder if a better term than "objective measure" is "probability".
> That carries the connotation that it represents the likelihood that
> something happens. Then you could have an objective probability which
> told how likely each universe was (its chance of being selected at
> random from the multiverse), and a subjective measure that told how
> much you cared about universes.

No, we need to reserve the word "probability" for the subjective level of
confidence that some statement is true. This is the classical baysian
definition, and I think it's still needed in the new decision theory, even
though I don't know how it will be used exactly. Basicly we still need a
theory that takes into account computational limitations, and perhaps in
order to do that we need to assign probabilities to mathmatical statements
so that you can say things like "P(3.14 < pi < 3.15) > .99999999" or
"P(event x happens in universe y) = z".
Received on Tue Jan 22 2002 - 16:51:53 PST