Re: computation vs definition (was: Kiln People)

From: Russell Standish <R.Standish.domain.name.hidden>
Date: Wed, 23 Jan 2002 12:05:05 +1100 (EST)

Wei Dai wrote:
>
> 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.
>

My view is that all infinite length descriptions exist in equal
measure, including the noncomputable ones. All observers induce a
natural (observer dependent) measure simply from the fact that
observers must categorise descriptions into equivalence classes of
identical meaning. In the case of observers being Turing machines, the
induced measure is one of the Universal Prior measures, but it is not
necessary to assume the observer is a Turing machine.

This of course differs from Schmidhuber's assumption that the ensemble
of descriptions must be generated by something with resource
constraints (ie that the induced measure is a convolution of the
observer induced measure, and the speed prior). This could be because
we inhabit a virtual reality for example. Nick Bostrom has explored
some arguments that indicate the likelihood of this.

I believe my position is the null hypothesis, against which
Schmidhuber's speed prior needs to be tested, whether by direct
experiment, or by a Bostrom-like doomsday argument. It is still an
open question as to whether this can be done...

                                                Cheers

----------------------------------------------------------------------------
Dr. Russell Standish Director High Performance Computing Support Unit,
Phone 9385 6967, 8308 3119 (mobile) UNSW SYDNEY 2052 Fax 9385 6965,
0425 253119 (") Australia R.Standish.domain.name.hidden Room 2075, Red Centre
http://parallel.hpc.unsw.edu.au/rks
            International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
Received on Tue Jan 22 2002 - 17:17:02 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST