599 views

Skip to first unread message

Jul 13, 2005, 11:14:05 PM7/13/05

to everyth...@eskimo.com

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

Jul 13, 2005, 11:55:27 PM7/13/05

to Wei Dai, everyth...@eskimo.com

Wei,

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,

A = P(
X is uncomputable)

should
be equal to

B =
P(X is uncomputable within resources I)

since
there is no evidence comprehensible by M that can distinguish A from
B.

Any
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
experience.

As 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
practice.

--
Ben

Jul 13, 2005, 11:55:29 PM7/13/05

to Wei Dai, everyth...@eskimo.com

Wei,

I
forwarded your post to a few of my colleagues, and one of them (Moshe Looks)
replied with basically the same solution as I already posted here, but in
different words...

Here
is his reply...

--
Ben

> 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

Jul 14, 2005, 1:05:22 AM7/14/05

to Ben Goertzel, everyth...@eskimo.com

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

>> 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.

Jul 14, 2005, 1:31:02 AM7/14/05

to Wei Dai, everyth...@eskimo.com

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

Jul 14, 2005, 5:57:49 PM7/14/05

to everyth...@eskimo.com

Wei Dai writes:

> 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.

> 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.

So in terms of induction, the situation is that we do test after test

to see if this box acts as a halting-problem oracle (HPO, we always

need more 3 letter acronyms around here). And it passes all the tests.

So then we apply induction and say, since it's acted like an HPO in our

tests, we will go ahead and assume that it really is an HPO.

The problem is that HPOs are theoretically impossible. We have a proof

of it, in fact we have a lot of proofs. So how do we reconcile this?

Well, one possibility is that the proof is invalid. It's a pretty

simple proof so we look at its assumptions. Fundamentally it assumes

that computation is a finitary process. We can only do a finite amount

of computation in a finite time.

To act as a real HPO it would seem to be necessary for the box in some

way to deal with infinities. There would have to be an actual infinity

in there somewhere.

But again, we generally assume that there are no actual infinities.

In physics they are called singularities, which means places where the

laws of physics break down. In fact even the prospect of an actual

infinity in a theory is seen as a sign that the theory is wrong or

incomplete. Relativity puts singularities at the center of black holes,

but it is assumed that quantum gravity will fix these, in fact this is

one of the main motivations for work on quantum gravity.

Disbelief in actual infinities, like disbelief in HPOs, is not really

rooted in observation and induction. We don't disbelieve in them simply

because our universe seems to be devoid of them. In fact, on the face

of things there is evidence that actual infinities may really exist in

our universe. Relativity theory has its infinites; there are quantum

models which hint at the possibility as well, and even old fashioned

Newtonian gravitation on point particles, like is studied in high school

physics, implicitly embeds infinities and can construct an HPO. But still,

nobody believes that this stuff will work. It's always assumed to be

a mistake which future work will correct. (Google hypercomputers or

super-Turing computers for some theoretical models of HPOs.)

So where does our disbelief come from? Why are we so skeptical? We don't

have very good grounds from observation. The mere fact that we've never

seen X isn't strong evidence that X doesn't exist. We discover new things

all the time, amazing things. Why should HPOs be any different?

It seems that our disbelief in HPOs and in other manifestations of

infinity is somehow rooted in mathematics itself. We have an instinctive

aversion to the possibility of an actual infinity existing as something

we can interact with. We believe that mathematics is essentially a

finite endeavor, at least in terms of how it manifests in the real world.

And yet there are plenty of mathematical models of infinities.

The study of transfinites is a very active part of set theory, in

fact it is entirely what makes set theory non-trivial. Likewise, with

the super-Turing work people have constructed hierarchies of ever more

powerful infinity machines. So there is no dearth of mathematical models

to deal with infinities.

In response to early work on transfinites the mathematical school called

constructivism arose. Constructivists reject most of mathematics that

deals with infinities. I am not too familiar with the history but I

believe that they were concerned about the many potential paradoxes

and the possibility that our intuition was a poor guide to truth in the

treacherous waters of the transfinites.

Constructionism has not gained much ground among mathematicians; I get the

impression that it's just not that much fun to do math that way. But it

seems to accord well with our instincts about the world. Perhaps we

could say that it is all very well for the mathematicians to construct

their transfinite castles in the air, but when it comes to reality,

we are constructionists.

> 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 see.

Our theories say that it can't happen. Yet in this case we have an

observation where it seems like it does happen. So what do we do?

It helps in the analysis to distinguish what people actually do from

what they "should" ideally do. People are imperfect reasoning machines

and there is no fundamental or theoretical interest in explicating every

detail of what they believe and what they don't. No doubt it would be

possible to build up a complete formal theory and model of a given human

brain that would fully explain how it does induction, full of complicated

rules and contradictions. That's not the interesting question.

The harder question is, what *should* we do, in this situation? I see

two possibilities.

One is to hold to our theories. No matter how many times we see

this machine work, we disbelieve it. We assume it is a trick.

Others have suggested ways the trickery might be done. It would be

extremely difficult and technologically challenging, but not impossible.

These tricks require effort that would be characterized by extremely

large numbers, but not infinities. If we are skeptical that they could

put such large numbers together, we should be infinitely more skeptical

that they can manage infinities.

The other possibility is to change our theories, and apply induction.

Faced with the evidence of a machine that seems to work, we accept that

maybe it really does work. And if so, then our theories are wrong and

we need new ones.

This is a hard course because of the peculiar grounding of the theories

involved. As described above, they aren't based on observation. They are

much more fundamental. They have to do with our deepest beliefs about the

nature of reality and perhaps even the nature of logic and mathematics.

It's questionable to me whether any finite set of observations in the real

world has the standing, the philosophical strength, to change our beliefs

about the nature of something as ethereal and unphysical as mathematics.

But maybe it's the right thing to do. After all, our imperfections,

our existence as creatures of a mundane reality, make us prone to error.

We might be wrong about anything. Arguably, an optimal induction engine

stands ready to change any and every one of its pre-existing beliefs,

when they are strongly enough contradicted by the evidence. So perhaps

we really should change our minds about mathematics, forget about that

constructionism nonsense, and accept that infinities exist and are real,

and here's one that we can touch and poke at.

> 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.

Are you confident that this is well defined? I understand Schmidhuber's

approach: pick an arbitrary UTM, run a random program through it, and take

the bit pattern that comes out as the information object. The fraction

of programs that produce a given information object is the measure.

Is there a similarly mechanical way of understanding the concept of

object description in the language of set theory? Can you sketch how

that would work?

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

The mainstream view, I gather, is that induction is indeed unformalizable.

The contrary claim, that induction can be formalized, would be considered

controversial.

Another way to express the problem is to think of trying to build an

optimal induction machine. It could use Bayes theorem to update its

beliefs, but what about the priors? Same problem. We could use the

Universal Prior but it gives probability 0 to HPOs. Then there are all

those other priors that implicitly assume infinite computation, so where

does it stop? There are no end to infinities, and as Wei's example shows,

there is apparently no place to stand once you start down that road.

It would be absurd to suggest, say, that everything up to Aleph-23

has Platonic existence, while infinities from Aleph-24 on up are mere

mysticism. Likewise, building a universe out of a UTM+HPO doesn't make

sense because as Wei says, there is a 2nd-order HPO, an HPO2, which is

beyond the scope of UTM+HPO, so what if the aliens show up with one

of those? For a multiverse model to make sense it has to be simple,

distinctive and (ideally) unique. We don't quite achieve uniqueness

with the UDist (due to the arbitrary choice of a UTM which creates a

multiplicative constant difference on measure), which is a major flaw.

But adding oracles makes the problem infinitely worse.

Here's what I conclude. If we really believe in the Universal

Distribution, then we ascribe probability zero to HPOs. That means

that in Wei's story, indeed the aliens are tricking Earth. If we try to

imagine a universe where the aliens are legitimate and have real HPOs,

that is impossible. We are just confusing ourselves if we think such a

universe could be real. There is no point in even considering thought

experiments based on it, any more than imagining what would happen if

aliens showed up with a logical formula which was obviously simultaneously

true and false. So given that we stand upon the UDist, there is no need

to pay much attention to these kinds of thought experiments.

I would suggest that evidence for or against the UDist should come

more from the fields of mathematics and logic than from any empirical

experience. My hope is that further study will lead to a computational

model which is distinguished by its uniqueness and lack of ambiguity.

That seems necessary for this kind of explanation of our existence to

be successful.

Hal Finney

Jul 15, 2005, 8:32:35 AM7/15/05

to Hal Finney, everyth...@eskimo.com

I make a comment on Wei Dai, as quoted by Hal Finney, and then I Hal

Finney's answer.

Le 14-juil.-05, à 23:03, Hal Finney a écrit :

> Wei Dai writes:

>> 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.

I recall that the comp hyp (I am a machine) entails that the apparent

universe cannot be the result of a computation (but can appear (first

personally) *through* the infinite execution of a non terminating

computation like UD* (the infinite trace of the Universal Dovetailer).

I have discussed this at length with Schmidhuber on this list, but he

dismissed the 1-3 difference so we were not able to progress.

>> 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.

>

> Hal Finney:So in terms of induction, the situation is that we do test

> after test

> to see if this box acts as a halting-problem oracle (HPO, we always

> need more 3 letter acronyms around here). And it passes all the tests.

> So then we apply induction and say, since it's acted like an HPO in our

> tests, we will go ahead and assume that it really is an HPO.

>

> The problem is that HPOs are theoretically impossible. We have a proof

> of it, in fact we have a lot of proofs. So how do we reconcile this?

I guess you mean that "testing HPO" is theoretically impossible. I

agree with comp. But some "hyperturing" thesis we could test HPO (the

fact that nobody can give a protocol for testing HPO in a finite time

suggests that "hyperturing thesis" could be non plausible.

>

> Well, one possibility is that the proof is invalid. It's a pretty

> simple proof so we look at its assumptions. Fundamentally it assumes

> that computation is a finitary process. We can only do a finite amount

> of computation in a finite time.

This is equivalent to the comp hyp.

>

> To act as a real HPO it would seem to be necessary for the box in some

> way to deal with infinities. There would have to be an actual infinity

> in there somewhere.

.. and in "our head" to understand the HPO. Note that a test exists in

the limit by computing the OMEGA Chaitin number (through an infinite

always self-correcting procedure which stabilize in a non constructive

way).

>

> But again, we generally assume that there are no actual infinities.

> In physics they are called singularities, which means places where the

> laws of physics break down. In fact even the prospect of an actual

> infinity in a theory is seen as a sign that the theory is wrong or

> incomplete. Relativity puts singularities at the center of black

> holes,

> but it is assumed that quantum gravity will fix these, in fact this is

> one of the main motivations for work on quantum gravity.

OK.

>

> Disbelief in actual infinities, like disbelief in HPOs, is not really

> rooted in observation and induction. We don't disbelieve in them

> simply

> because our universe seems to be devoid of them. In fact, on the face

> of things there is evidence that actual infinities may really exist in

> our universe. Relativity theory has its infinites; there are quantum

> models which hint at the possibility as well, and even old fashioned

> Newtonian gravitation on point particles, like is studied in high

> school

> physics, implicitly embeds infinities and can construct an HPO.

That is right. Mathematically HPO and actual infinities are not

obviously inconsistent. They are obviously consistent for those who

believe in the consistency of ZF (Zermelo Fraenkel Set Theory).

> But still,

> nobody believes that this stuff will work. It's always assumed to be

> a mistake which future work will correct. (Google hypercomputers or

> super-Turing computers for some theoretical models of HPOs.)

(Note, in passing, that G and G* remains sound and complete for those

hyper-turing machine. Actually what I call comp could be called in that

contest omega-comp. I think (but don't have a full detailed proof of

it) that for all constructive (Church-Kleene) ordinal alpha, the logic

of self-reference (G and G*) remains stable for alpha-comp. Solovay's

proof makes it possible to get proper extensions of G and G* for

strong, non constructivist generalization of provability, like "being

true in all *transitive* models of ZF".

Of course ""being true in just all models of ZF", is equivalent, by

Godel's COMPLETENESS (not incompleteness) theorem to provable in ZF,

and this leads to completeness and soundness of G and G*.

Let me quote the footnote 28 of mùy sane paper:

[G and G* are sound and complete for larger systems, and can be

enriched for providing non-comp notion of belief, for example Solovay

got that G together with the formulas B(BX->BY) v B(BY->(BX&X)) gives a

system which is sound and complete for the (set theory) propositions

which are true in all transitive models of ZF (Zermelo Fraenkel set

theory). For a proof see Boolos 1993. Solovay got also that G together

with the formulas B(BX->Y)vB((BY &Y)->X) captures in the same way the

propositions true in all models VKappa with kappa an inaccessible

(rather big) cardinal. In case we find, as a measure on the consistent

histories, a consistent subset of physics, but don’t find all of

physics, making comp false, similar Solovay extensions of G and G*

could provide psychologies of some “non machine” notions. See R. M.

Solovay (1976): “Provability Interpretation of Modal Logic,” Israel

Journal of Mathematics, 25:287-304.]

>

> So where does our disbelief come from? Why are we so skeptical? We

> don't

> have very good grounds from observation. The mere fact that we've

> never

> seen X isn't strong evidence that X doesn't exist. We discover new

> things

> all the time, amazing things. Why should HPOs be any different?

>

> It seems that our disbelief in HPOs and in other manifestations of

> infinity is somehow rooted in mathematics itself. We have an

> instinctive

> aversion to the possibility of an actual infinity existing as something

> we can interact with. We believe that mathematics is essentially a

> finite endeavor, at least in terms of how it manifests in the real

> world.

Note that you talk a little bit as you were (again?) postulating the

existence of a real world, when in other post you acknowledge the

interest of deriving it from the observer-moments.

>

> And yet there are plenty of mathematical models of infinities.

> The study of transfinites is a very active part of set theory, in

> fact it is entirely what makes set theory non-trivial.

> Likewise, with

> the super-Turing work people have constructed hierarchies of ever more

> powerful infinity machines. So there is no dearth of mathematical

> models

> to deal with infinities.

>

> In response to early work on transfinites the mathematical school

> called

> constructivism arose. Constructivists reject most of mathematics that

> deals with infinities. I am not too familiar with the history but I

> believe that they were concerned about the many potential paradoxes

> and the possibility that our intuition was a poor guide to truth in the

> treacherous waters of the transfinites.

>

> Constructionism has not gained much ground among mathematicians;

The problem for the constructionist is that the work they do find

terribly interesting applications in non-constructive mathematics!

There is a fertile back and forth between constructive and

non-constructive mathematics.

> I get the

> impression that it's just not that much fun to do math that way. But

> it

> seems to accord well with our instincts about the world. Perhaps we

> could say that it is all very well for the mathematicians to construct

> their transfinite castles in the air, but when it comes to reality,

> we are constructionists.

This is *very* debatable.

1) A down to earth problem on the braids group has been solved by using

large cardinals.

2) Girard succeeds in blurring the distinction between constructive/non

constructive. In some sense classical linear or quantum logics are

more constructive than constructive linear logics.

3) George Boolos, commenting a solution of a puzzle by Smullyan, shows

that decision theory needs non classical thought (like the excluded

middle principle).

>

>

>> Wei Dai: Fortunately, the Artificial Intelligence in charge of

But concerning the HPO I don't think we can do the test at all. We

cannot know if the machine does the trick. If the machine solves and

give the proof for the first 2^64 math problems corresponding to the 64

first digit of Chaitin OMEGA, all we can conclude is that they are very

advanced in math. Testing an HPO box just measure the advance of the

extraterrestrial math. Even if they open the box and show us it is not

just a summary (-la-OMEGA-Chaitin's way) of their "annals of

mathematics", we will not been able to understand it, or if we do, then

the extra-terrestrial will indeed refute Church thesis and comp.

> Others have suggested ways the trickery might be done. It would be

> extremely difficult and technologically challenging, but not

> impossible.

> These tricks require effort that would be characterized by extremely

> large numbers, but not infinities. If we are skeptical that they could

> put such large numbers together, we should be infinitely more skeptical

> that they can manage infinities.

>

> The other possibility is to change our theories, and apply induction.

> Faced with the evidence of a machine that seems to work, we accept that

> maybe it really does work. And if so, then our theories are wrong and

> we need new ones.

>

> This is a hard course because of the peculiar grounding of the theories

> involved. As described above, they aren't based on observation. They

> are

> much more fundamental. They have to do with our deepest beliefs about

> the

> nature of reality and perhaps even the nature of logic and mathematics.

> It's questionable to me whether any finite set of observations in the

> real

> world has the standing, the philosophical strength, to change our

> beliefs

> about the nature of something as ethereal and unphysical as

> mathematics.

I agree, at least for a large part of math.

Well, Tegmark tried but did not succeed. Of course you can list the

definition of set object or of set of proof. But then "computationnaly"

is it like working in very weak theory, and concerning proof, well this

is not "closable" for the diagonalization procedure so this is

"forever" a relative concept. Formally, if the proofs are checkable (in

finite time) the invariant you can capture is already given by G and

G*.

>

>

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

>

> The mainstream view, I gather, is that induction is indeed

> unformalizable.

> The contrary claim, that induction can be formalized, would be

> considered

> controversial.

Right, but this does not prevent mathematical analysis.

>

> Another way to express the problem is to think of trying to build an

> optimal induction machine. It could use Bayes theorem to update its

> beliefs, but what about the priors? Same problem. We could use the

> Universal Prior but it gives probability 0 to HPOs. Then there are all

> those other priors that implicitly assume infinite computation, so

> where

> does it stop? There are no end to infinities, and as Wei's example

> shows,

> there is apparently no place to stand once you start down that road.

Mmh..., Prior, Bayes, ... required ASSA. But comp needs RSSA. (old

discussion).

>

> It would be absurd to suggest, say, that everything up to Aleph-23

> has Platonic existence, while infinities from Aleph-24 on up are mere

> mysticism. Likewise, building a universe out of a UTM+HPO doesn't make

> sense because as Wei says, there is a 2nd-order HPO, an HPO2, which is

> beyond the scope of UTM+HPO, so what if the aliens show up with one

> of those?

This rejoins my critics of Tegmark.

> For a multiverse model to make sense it has to be simple,

> distinctive and (ideally) unique. We don't quite achieve uniqueness

> with the UDist (due to the arbitrary choice of a UTM which creates a

> multiplicative constant difference on measure), which is a major flaw.

> But adding oracles makes the problem infinitely worse.

>

> Here's what I conclude. If we really believe in the Universal

> Distribution, then we ascribe probability zero to HPOs.

I agree, except that methodologically, once we accept Church thesis,

this is not something we can decide, we must prove that there is no

other choice.

> That means

> that in Wei's story, indeed the aliens are tricking Earth.

Most probably (unless not comp).

> If we try to

> imagine a universe where the aliens are legitimate and have real HPOs,

> that is impossible. We are just confusing ourselves if we think such a

> universe could be real. There is no point in even considering thought

> experiments based on it, any more than imagining what would happen if

> aliens showed up with a logical formula which was obviously

> simultaneously

> true and false. So given that we stand upon the UDist, there is no

> need

> to pay much attention to these kinds of thought experiments.

Nor with the UD ;)

>

> I would suggest that evidence for or against the UDist should come

> more from the fields of mathematics and logic than from any empirical

> experience.

Yes.

> My hope is that further study will lead to a computational

> model which is distinguished by its uniqueness and lack of ambiguity.

> That seems necessary for this kind of explanation of our existence to

> be successful.

ASSA + Udist: I doubt it can work. But who knows?

RSSA + UD: they are "concrete" evidence it works. No?

Bruno

Jul 15, 2005, 1:27:50 PM7/15/05

to everyth...@eskimo.com

One question I am uncertain about is this: how well could we test a

supposed halting-problem oracle (HPO) box?

supposed halting-problem oracle (HPO) box?

In particular I wonder, suppose it turns out that P=NP and that further

there is an efficient algorithm to solve any NP problem. For those

unfamiliar with this terminology P means polynomial time, and we say

that problems in P can be solved efficiently. NP means nondeterministic

polynomial time, and essentially this means that for problems in NP, we

can efficiently test a purported solution for correctness. Whether P

is equal to NP or merely a subset of it is one of the major unsolved

problems of computer science.

But what if the aliens have solved it, and (somewhat to our surprise)

the answer is that every NP problem can be efficiently solved. And they

have embedded this NP solving algorithm (along with some other ones)

in the HPO box.

My concern is that to test the HPO box we could for example give it

a problem we have solved and see if it gets the answer. But success

might just imply that the HPO had substantially (but not astronomically)

greater computing power than the human race can bring to bear. Or we

could give it a problem we can't solve and then check the answer the

HPO gives, but if the answer is testable that would mean it is in NP,

and so even success in this area could be explained if P=NP as above.

It is much less philosophically challenging to imagine that P=NP than

to imagine that a true HPO could exist. Things would be different if

we ever get a proof that P < NP but we aren't in that situation now.

Are there other tests we could give, harder ones, that could give us

evidence that it was a true HPO, that could not be fooled by an NP solver?

My knowledge of these areas is pretty spotty. The only non NP problem I

know of offhand is the travelling salesman problem, finding the shortest

path visiting everyone of a set of cities with specified distances

between each pair. Proposed solutions cannot be tested efficiently,

as far as I know. If the box solved travelling salesmen problems for

us, it might be a boon to salesmen but we would not necessarily know if

we were getting truly optimal paths.

So in Wei's story, when the scientists go to test the HPO box, how strong

is the evidence that they can reasonably expect to get for it being a

real HPO? And I suppose a practical point arises as well; even if it

is not a true HPO, if it is nevertheless able to solve every problem we

give it, it's probably worth the money!

Hal Finney

Jul 15, 2005, 2:55:53 PM7/15/05

to Ben Goertzel, Wei Dai, everyth...@eskimo.com

Ben Goertzel:

> 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...

> 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...

Imo, induction only works when the complexity

of the data is not larger than the complexity

of the theorem (or the model, or the theory,

etc.) we wish to prove. In other words, if those

data are special, induction does not work.

Isn't this another parameter for that formalization?

-serafino

Jul 16, 2005, 10:06:58 AM7/16/05

to scerir, Wei Dai, Ben Goertzel, everyth...@eskimo.com

Le 15-juil.-05, à 20:55, scerir a écrit :

Actually this is a subject of a whole sub-branch of theoretical

computer science called Computational Learning Theory.

You are right that automated induction cannot work on sequences as

complex as they minimal description, but you are optimist if you think

the reverse is true, at least in term of class of sequences

recognizable by a unique machine. (An individual computable sequence is

always trivially inferable if only by the stupid machine which knows

only the program of that sequence, so the interesting notion in

learning theory is the learning of class of sequences (or of computable

total function). A class of sequence is learnable by a machine if for

any sequence taken from that class and presented by finite pieces the

machine eventually (after a finite time) output a program predicting or

computing the sequence.

The class of ALL computable sequences (or the set of computable total

functions) cannot be recognized in that sense by any learning machine.

By using genuinely the notion of "dovetailing" it is not hard to show

that all Recursively (Mechanically) Enumerable set of computable total

function can be learned.

By weakening the criteria of identification, some hierarchies of

learnable class can be studied.

Putnam and Popper have wrote some important prehistorical papers.

Important works by BLUM. But also by Blum and Blum. Blum wrote with her

husband the paper on the "NON UNION THEOREM", which, roughly speaking,

says that if you evaluate intelligence of machine by the learnable

class, then (in a sense) What is uncomputably more intelligent than a

machine? Two machines! (where a sequence is recognize if one of the two

machine get the correct predicting program).

BLUM L. & BLUM M., 1975, Toward a Mathematical Theory of Inductive

Inference. Information and Control 28,.pp. 125-155.

My favorite paper (a classical one):

CASE J. & SMITH C., 1983, Comparison of Identification Criteria for

Machine Inductive Inference. In Theoretical Computer Science 25,.pp

193-220.

A book (there is a new edition quite augmented by I have not the

reference):

OSHERSON D.N., STOB M.and WEINSTEIN S., 1986, Systems that Learn, MIT

press.

See also:

http://www.cis.udel.edu/~case/colt.html and links therein,

See perhaps a short summary of the main result by Case & Smith in the

section 5.2 of:

http://iridia.ulb.ac.be/~marchal/publications/M&PI_15-MAI-91.pdf

Bruno

http://iridia.ulb.ac.be/~marchal/

Jul 22, 2005, 5:39:57 AM7/22/05

to everyth...@eskimo.com, "Hal Finney"

Couple of comments to the post below.

1. P=?NP is a purely mathematical problem, whereas the existence of an HPO

box is an emperical matter. If we had access to a purported HPO box while

P=?NP is still unsolved, we can use the box to exhaustively search for

proofs of either P=NP or P<NP.

2. I think it's very unlikely that P=NP, but in case it is, we can still

test an HPO box by generating random instances of hard problems with known

solutions. (That is, you generate a random solution first, then generate a

random problem with that solution in mind.) For example here's a page about

generating random instances of the Traveling Salesman Problem with known

optimal solutions.

http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html

----- Original Message -----

From: ""Hal Finney"" <h...@finney.org>

To: <everyth...@eskimo.com>

Sent: Saturday, July 16, 2005 12:29 AM

Subject: Re: is induction unformalizable?

Jul 22, 2005, 1:40:23 PM7/22/05

to everyth...@eskimo.com, h...@finney.org, wei...@weidai.com

Wei Dai writes:

> 1. P=?NP is a purely mathematical problem, whereas the existence of an HPO

> box is an emperical matter. If we had access to a purported HPO box while

> P=?NP is still unsolved, we can use the box to exhaustively search for

> proofs of either P=NP or P<NP.

> 1. P=?NP is a purely mathematical problem, whereas the existence of an HPO

> box is an emperical matter. If we had access to a purported HPO box while

> P=?NP is still unsolved, we can use the box to exhaustively search for

> proofs of either P=NP or P<NP.

I've seen many speculations that P=?NP may be undecideable under our

current axioms. I guess this is because people are tired of looking

for proofs and PhD students don't want to get assigned this problem.

I'm not sure whether both of the following possibilities would be

consistent with the issue being undecideable:

A: There actually exists a polynomial-time algorithm to solve all

NP problems, but we can't prove that it always works, even though it

always does.

B: There is no polynomial time algorithm that solves all NP problems,

but we can't prove that no such algorithm exists.

I wonder if we could ask the HPO (halting problem oracle) box any harder

questions, that might help resolve the issue if it turned out that P=NP

is undecideable. Could we use it to directly ask whether the algorithm

in case A above exists, and perhaps even to find it?

> 2. I think it's very unlikely that P=NP, but in case it is, we can still

> test an HPO box by generating random instances of hard problems with known

> solutions. (That is, you generate a random solution first, then generate a

> random problem with that solution in mind.) For example here's a page about

> generating random instances of the Traveling Salesman Problem with known

> optimal solutions.

>

> http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html

That's a good idea, but is it known that this subset of problems is

still NP-hard? I would worry that problems like these, where a fractal

or space-filling curve type of path is the right solution, might turn

out to be easier to solve than the general case.

Hal Finney

Jul 22, 2005, 2:41:34 PM7/22/05

to everyth...@eskimo.com

Dear Hal and Wei Dai,

One question: Does it not make sense that if there did exist an instance

of a P=NP computation within our physical universe that Nature would not

have found a way to implement it widely? The fact that the folding of

proteins, a known NP complete problem, takes a relatively long time to

actually occur tells me that such a computation, at best, only occurs is

very special situations in our universe, situations that can not be

converted (via a polynomial transformation) to solve problems in other

situations.

There is an old saying: What ever Man can do, Nature is already doing,

better.

Nature is performing computations all the time and what we experience is

the best computation possible.

It is only our failure of imagination that leads us to endlessly follow

rabbit trails. ;-)

Kindest regards,

Stephen

----- Original Message -----

From: ""Hal Finney"" <h...@finney.org>

To: <everyth...@eskimo.com>; <h...@finney.org>; <wei...@weidai.com>

Sent: Friday, July 22, 2005 12:43 PM

Subject: Re: is induction unformalizable?

Jul 22, 2005, 6:29:50 PM7/22/05

to everyth...@eskimo.com

But I'm not sure what it would mean for an instance of P=NP

computation to exist in nature. What it would mean in computer

science is that there was an algorithm for translating any NP

algorithm into a P algorithm for the same problem. This refers

to classes of algorithms for classes of problems. If you observe

a certain instance of protein folding - that's not an algorithm.

If you study many instances of protein folding you may develop an

algorithm that will predict how a class of proteins will fold and

that may scale as NP. Someone else might find another algorithm

that scales as P. But that's not the same as finding a way of

translating any NP algorithm into a P one. And neither one shows

that nature is using an algorithm. Nature isn't predicting how a

class of proteins is going to fold - it's just folding a few

specific examples.

computation to exist in nature. What it would mean in computer

science is that there was an algorithm for translating any NP

algorithm into a P algorithm for the same problem. This refers

to classes of algorithms for classes of problems. If you observe

a certain instance of protein folding - that's not an algorithm.

If you study many instances of protein folding you may develop an

algorithm that will predict how a class of proteins will fold and

that may scale as NP. Someone else might find another algorithm

that scales as P. But that's not the same as finding a way of

translating any NP algorithm into a P one. And neither one shows

that nature is using an algorithm. Nature isn't predicting how a

class of proteins is going to fold - it's just folding a few

specific examples.

Brent Meeker

On 22-Jul-05, you wrote:

> Hi Brent,

>

> You make a very good point and I agree with you completely!

> But I am arguing that it is the distinction between physical and

> abstract systems that seems to require some closer examination,

> and a slightly different point. If we are going to use arguments

> that are only "in principle"based to make decisions about

> situations in the physical world, does it not follow that we

> might be making serious errors?

> My claim stands!

>

> "... if there did occurs an instance of a P=NP computation

> within our physical universe then it follows that Nature would

> have found a way to implement it widely."

>

> If "P=NP Oracles" are allowed at all in our physical

> universe, then it follows that some evidence could be found of

> their occurance. If they can only exist in the very special case

> of an abstract universe, what connection do they have with

> physics or anything other than metaphysics?

>

> Stephen

>

> PS. Please cc your reply to the Everything List, I am sure that

> others are interested in this thread.

>

> ----- Original Message -----

> From: "Brent Meeker" <meek...@rain.org>

> To: "Stephen Paul King" <step...@charter.net>

> Sent: Friday, July 22, 2005 3:07 PM

> Subject: Re: is induction unformalizable?

>

>

>> On 22-Jul-05, you wrote:

>>

>>> Dear Brent,

>>

>> Could you name some examples? In the real world,

>> computations obey the laws of thermodynamics, among other

>> things, thus for problems with the same number of independent

>> degrees of freedom, the P problems can be computed faster

>> than

>> the NP. Of course this is just an average, but baring some

>> counter-examples I fail to understand your point.

>>

>> Stephen

>>

>> The laws of thermodynamics apply to physical processes, not

>> abstractions like algorithms. Of course computations are

>> physical processes - but P and NP are classes of algorithms,

>> not

>> computations. I'll see if I can find some specific examples,

>> but

>> the general point is that a polynomial algorithm may have a

>> large

>> fixed cost and then scale, say, linearly with the size of the

>> problem; while another algorithm for the same class of problem

>> may have a small fixed cost yet scale exponentially. Then up

>> to

>> some size (which may be very large) the latter will be faster

>> than the former. It is only in the limit of infinite size that

>> a

>> P algorithm is necessarily faster than an NP one. Since all

>> examples from Nature are finite, you can't infer that Nature

>> must

>> have found P algorithms for problems we think are NP.

>>

>> Brent Meeker

>>

>

>

Regards

--

Brent Meeker

Jul 22, 2005, 7:47:20 PM7/22/05

to everyth...@eskimo.com

Hi Brent,

Ok, I am rapidly loosing the connection that abstract models have with

the physical world, at least in the case of computations. If there is no

constraint on what we can conjecture, other than what is required by one's

choice of logic and set theory, what relation do mathematical models have

with reality?

Is this not as obvious as it appears?

BTW, Scott Aaronson has a nice paper on the P=NP problem that is found here:

http://www.scottaaronson.com/papers/npcomplete.pdf

I recommend this paper as well:

http://www.scottaaronson.com/papers/are.ps

Kindest regards,

Stephen

Jul 22, 2005, 11:21:50 PM7/22/05

to everyth...@eskimo.com

On 22-Jul-05, you wrote:

> Hi Brent,

>

> Ok, I am rapidly loosing the connection that abstract models

> have with the physical world, at least in the case of

> computations. If there is no constraint on what we can

> conjecture, other than what is required by one's choice of logic

> and set theory, what relation do mathematical models have with

> reality?

>

> Is this not as obvious as it appears?

Here's my $0.02. We can only base our knowledge on our experience

and we don't experience *reality*, we just have certain

experiences and we create a model that describes them and

predicts them. Using this model to predict or describe usually

involves some calculations and interpretation of the calculation

in terms of the model. The relation of the model to reality, if

it's a good one, is it gives us the right answer, i.e. it

predicts accurately. Their are other criteria for a good model

too, such as fitting in with other models we have; but prediction

is the main standard. So in my view, mathematics and theorems

about computer science are just models too, albeit more abstract

ones. Persis Diaconsis says, "Statistics is just the physics of

numbers." I have a similar view of all mathematics, e.g.

arithmetic is just the physics of counting.

Brent Meeker

Jul 23, 2005, 12:27:28 AM7/23/05

to everyth...@eskimo.com

I would like to suggest a way of reconciling this situation for your consideration. I have no proof as yet but if accepted and then used as a vehicle of exploration and understanding of context I have found it to be a useful.

A formal logic (an arbitrary calculus) is defined by 4 basic constituents:

1) signs

2) rules of formation

3) rules of inference

4) rules of transformation

Basically it's a formally specific grammar of signs.

A formal proof is a collection of (3) transformed according to (4) that takes the original inference from a starting state to an end state. Whatever state results is necessarily true according to the language.

The concept that I have found useful is that if you imagine that in some context in the universe, the natural behaviour of it happens to correspond to a virtual definition of items 1, 2, 3, 4 above, then what will be found is the universe behaving like formal logic of a certain type. Voila, mathematical decriptions are found to be 'unreasonably effective' ways of characterising the universe.

In different contexts in the natural world, difference sets of formal logic happen to be 'virtually reified' by the circumstances. In each case a different set of rules will be found. A slithly differrent set of mathematical rules will be found and we will tend to think that the 'laws' thus 'discovered' are somehow driving the universe.

In formal mathematics, though, one set of formalities can be transformed into anouther. Arithmetic can be done using formal logic, for example. Extraordinalrily tedious..but can be done...In a sense there is no 'native tongue', there are only 'tongues'.

When you think about it this way you end up wondering what is the 'calculus' of the natural world, which is selectively mapped into other calculii we find so useful? This brings in the idea of the universe as a reified calculus. Indeed the _only_ reified calculus. If it is, then what are its signs, rules of formation, inference, transformation?

I have been looking into this and I have been able to make on. I wonder if others can. Try it. I called mine 'entropy calculus'.

The idea brings with it one unique aspect: none of the calculii we hold so dear, that are so wonderful to play with, so poweful in their predictive nature in certain contexts, are ever reified. None of them actually truly capture reality in any way. They only appear to in certain contexts. The only actual mathematics that captures the true nature of the universe is the universe itself as a calculus. It doesn't invalidate the maths we love. It just makes it merely a depiction in a certain context. Very useful but thats all.

But there's a further subtlelty to this.

In mathematics there is a cultural assumption born of the history of mathematics.

..imagine Leibniz or Newton sitting there with their new toy calculus. They start with one set of symbols and work in a single line, transformation after transformation. A single linear proof emerges. Wonderment ensues.

If the universe is a calculus, how many Newtons and Leibniz's are there _All_ working at once? How many 'proofs' are being evaluated at once, all with direct relationships to each other?

Nobody ever thinks about that. If 100,000,000,000,000 leibnizs all started with their own sign and then connected with each other, formed, inferred transformed, each finding the results of the other 99,999,999,999,999 Leibniz's results in some way available to use in their own next transformation, what would the resulting calculus look like? What would it be like to 'be' one the proofs being enacted by Leibniz 145,735,365,268?

Leibniz 145,735,365,268's proof could be an electron. Leibniz 567,145,735,365,268's proof could be Bruno Marchal.

Our mathematics, as we see it, thinking about it from this perspective, is rather lame, n'est pas? Food for thought, anyway.

That's my handle on the relationship between mathematical models and reality. It's been a useful way of thinking for me and I commend it to you for a little amusement.

cheers

colin hales

Jul 23, 2005, 3:09:37 AM7/23/05

to everyth...@eskimo.com

Colin Hales writes:

> The idea brings with it one unique aspect: none of the calculii we

> hold so dear, that are so wonderful to play with, so poweful in their

> predictive nature in certain contexts, are ever reified. None of them

> actually truly capture reality in any way. They only appear to in

> certain contexts. The only actual mathematics that captures the true

> nature of the universe is the universe itself as a calculus. It doesn't

> invalidate the maths we love. It just makes it merely a depiction in a

> certain context. Very useful but thats all.

> The idea brings with it one unique aspect: none of the calculii we

> hold so dear, that are so wonderful to play with, so poweful in their

> predictive nature in certain contexts, are ever reified. None of them

> actually truly capture reality in any way. They only appear to in

> certain contexts. The only actual mathematics that captures the true

> nature of the universe is the universe itself as a calculus. It doesn't

> invalidate the maths we love. It just makes it merely a depiction in a

> certain context. Very useful but thats all.

You might like this quote from John Wheeler, in his textbook Gravitation written

with Charles Misner and Kip Thorne, which perhaps expresses a similar idea:

: Paper in white the floor of the room, and rule it off in one-foot

: squares. Down on one's hands and knees, write in the first square

: a set of equations conceived as able to govern the physics of the

: universe. Think more overnight. Next day put a better set of equations

: into square two. Invite one's most respected colleagues to contribute

: to other squares. At the end of these labors, one has worked oneself

: out into the door way. Stand up, look back on all those equations,

: some perhaps more hopeful than others, raise one's finger commandingly,

: and give the order `Fly!' Not one of those equations will put on wings,

: take off, or fly. Yet the universe 'flies'.

My current view is a little different, which is that all of the equations

"fly". Each one does come to life but each is in its own universe,

so we can't see the result. But they are all just as real as our own.

In fact one of the equations might even be our own universe but we can't

easily tell just by looking at it.

Hal Finney

Jul 23, 2005, 4:11:33 AM7/23/05

to everyth...@eskimo.com

"Hal Finney" writes:

>

> : Paper in white the floor of the room, and rule it off in one-foot

> : squares. Down on one's hands and knees, write in the first square

> : a set of equations conceived as able to govern the physics of the

> : universe. Think more overnight. Next day put a better set of equations

> : into square two. Invite one's most respected colleagues to contribute

> : to other squares. At the end of these labors, one has worked oneself

> : out into the door way. Stand up, look back on all those equations,

> : some perhaps more hopeful than others, raise one's finger commandingly,

> : and give the order `Fly!' Not one of those equations will put on wings,

> : take off, or fly. Yet the universe 'flies'.

>

> My current view is a little different, which is that all of the equations

> "fly". Each one does come to life but each is in its own universe,

> so we can't see the result. But they are all just as real as our own.

> In fact one of the equations might even be our own universe but we can't

> easily tell just by looking at it.

>

> Hal Finney

>

> : Paper in white the floor of the room, and rule it off in one-foot

> : squares. Down on one's hands and knees, write in the first square

> : a set of equations conceived as able to govern the physics of the

> : universe. Think more overnight. Next day put a better set of equations

> : into square two. Invite one's most respected colleagues to contribute

> : to other squares. At the end of these labors, one has worked oneself

> : out into the door way. Stand up, look back on all those equations,

> : some perhaps more hopeful than others, raise one's finger commandingly,

> : and give the order `Fly!' Not one of those equations will put on wings,

> : take off, or fly. Yet the universe 'flies'.

>

> My current view is a little different, which is that all of the equations

> "fly". Each one does come to life but each is in its own universe,

> so we can't see the result. But they are all just as real as our own.

> In fact one of the equations might even be our own universe but we can't

> easily tell just by looking at it.

>

> Hal Finney

Hi Hal,

Your 'flying equations' sound a bit like the idealist 'a-priori'... interesting but different topic for another day. :-) Thanks for the wheeler link....

On that note I'm not sure Wheeler's description is the same. In my idea of the calculus all there is is the sheets of paper. There are no symbols (no intrinsic representation). There are intrinsic rules of formation and transformation that relate and associate the bits of paper. If the bits of paper were jigsaw pieces with implicit connective rules then it is more like my idea.

If you try an build a universe as a monism from an enormous quantity of only one thing (a primitive sign - piles of little bits of paper :) ) then you can construct space and the leftovers become the stuff we call matter. Deep down it's all the one thing, however. It's been a fascinating mental exercise for me.

The problem is to let go of all the maths in a symbolic sense. We have this huge and very historically justified tendency to think the linear maths is the 'real stuff' of the natural world. I have been able to think of ways in which that is not the case, but that look 'as if' it was. It doesn't invalidate our maths, it just makes it look like it's not justified to ascribe anything more to the existence of our maths than that of a useful limited description.

The main thing is to get used to the idea of ridding your preconceptions of symbolic 'aboutness'. There is no intrinsically meaningful sign. However an intrinsic event: the expression of the sign (any sign), can literally be a truth in itself. The fact of the utterance of the sign itself is a truth. From that all other truths can be expressed through meaningless signs combining through intrinsic properties (affinities) for other signs.

It's more like a reified mega-dimensional cellular automata, actually. Not a traditional computational one. It took me a long time to be able to let go of my symbolic mathematical tendencies when I needed to.

You can make our universe out of hierarchically structured noise starting from nothing. The 'sign' in the calculus is basically the elemental noise event of the entropy calculus I have played with. Stuff that looks like the rules of quantum mechanics appears well up the hirearchy. Waaaaaay up the hierarchy it looks ontological but with structure all the way down to the elemental signs. The one that makes us is somewhere between 15? and 40? organisational layers deep. Very busy, these Leibniz's !!

Lots of fun! Don't know what to make of it but at least it has enabled me to post to this thread with a little bit of novelty!

cheers

colin

Jul 23, 2005, 9:57:05 PM7/23/05

to everyth...@eskimo.com

Hi Brent,Sent: Friday, July 22, 2005 8:31 PM

Subject: Re: what relation do mathematical models have with reality?

Subject: Re: what relation do mathematical models have with reality?

> On 22-Jul-05,Stephen P. King wrote:

>

>> Hi Brent,

>>

>> Ok, I am rapidly loosing the connection that abstract models

>> have with the physical world, at least in the case of

>> computations. If there is no constraint on what we can

>> conjecture, other than what is required by one's choice of logic

>> and set theory, what relation do mathematical models have with

>> reality?

>>

>> Is this not as obvious as it appears?

> [BM]

> Here's my $0.02. We can only base our knowledge on our experience

> and we don't experience *reality*, we just have certain

> experiences and we create a model that describes them and

> predicts them. Using this model to predict or describe usually

> involves some calculations and interpretation of the calculation

> in terms of the model. The relation of the model to reality, if

> it's a good one, is it gives us the right answer, i.e. it

> predicts accurately. Their are other criteria for a good model

> too, such as fitting in with other models we have; but prediction

> is the main standard. So in my view, mathematics and theorems

> about computer science are just models too, albeit more abstract

> ones. Persis Diaconsis says, "Statistics is just the physics of

> numbers." I have a similar view of all mathematics, e.g.

> arithmetic is just the physics of counting.

[SPK]

Ok, I would agree completely with you if we are using Kant's definition

of *reality*- Dasein: existence in itself, but I was trying to be point out

that we must have some kind of connection between the abstract and the

concrete.

One thing that I hope we all can agree upon about *reality* is that what

ever it is, its properties are invariant with respect to transformations

from one point of view to any other. It is this trait that makes it

"independent", but the problems with realism seem to arise when we consider

whether or not this *reality* has some set of properties to the exclusion of

any others independent of some observational context.

QM demands that we not treat objects as having some sharp set of

properties independent of context and thus the main source of

counterintuitive aspects that make QM so difficult to deal with when we

approach the subject of Realism. OTOH, we have to come up with an

explanation of how it is that our individual experiences of a world seem to

be confined to sharp valuations and the appearance of property definiteness.

Everett and others gave us the solution to this conundrum with the MWI. Any

given object has eigenstates (?) that have eigenvalues (?) that are sharp

and definite relative to some other set of eigenstates, but as a whole a

state/wave function is a superposition of all possible.

So, what does this mean? We are to take the a priori and context

independent aspect of *reality* as not having any one set of sharp and

definite properties, it has a superposition of all possible. The trick is to

figure out a reason why we have one basis and not some other, one

partitioning of the eigenstates and not some other.

What does this have to do with mathematics and models? If we are going

to create/discover models of what we can all agree is sharp and definite-

our physical world, we must be sure that our models agree with each other.

This, of course, assumes that there is some connection between abstract and

concrete aspect of *reality*.

Stephen

Jul 24, 2005, 1:24:53 AM7/24/05

to everyth...@eskimo.com

On 23-Jul-05, you wrote:

MWI is *a* solution. But it is also possible to regard QM as a theory of

what we know or can say about a system. Have you read Bohm's

interpretation of QM? MWI seemed very promising when it seemed to solve

the Born problem. But since it has been shown that the Born postulate is

independent, then one might as well postulate that only one thing happens -

as in consistent histories, or Bohm's intepretation.

>Any given object has eigenstates (?) that have eigenvalues

> (?) that are sharp and definite relative to some other set of eigenstates,

> but as a whole a state/wave function is a superposition of all possible.I

I'm not sure what you mean by "object". In general an object, such as an

electron, has different eigenvalues depending on how it is

prepared/measured. So they are not necessarily properties of the object

alone.

> So, what does this mean? We are to take the a priori and context

> independent aspect of *reality* as not having any one set of sharp and

> definite properties, it has a superposition of all possible.

That's not how I'd take it.

>The trick is

> to figure out a reason why we have one basis and not some other, one

> partitioning of the eigenstates and not some other.

That's the decoherence program of Zeh, Zurek, Joos, Schlosshauer, et al.

>

> What does this have to do with mathematics and models? If we are going

> to create/discover models of what we can all agree is sharp and definite-

> our physical world, we must be sure that our models agree with each other.

> This, of course, assumes that there is some connection between abstract

> and concrete aspect of *reality*.

Or that we pick out those parts of our experience which we can describe by

models indpendent of viewpoint. The rest we call subjective experience.

Brent Meeker

Jul 24, 2005, 2:21:25 AM7/24/05

to everyth...@eskimo.com

Greetings,

Here's my Rupee 1 on the connection between "abstract models" and "reality";

Although it is ofcourse debatable, I hold that what we call reality is

our minds' "understanding" of our sensory perceptions. Thus the notion

of (our) reality depends on:

1. The nature of mind

Let's assume that the mind is simply the brain + the processes the

brain is capable of + the information it stores/processes. Then the

nature of the mind is the (sub)set of data-structures and computations

that the brain is capable of.

2. The process of "understanding"

Using the above informal definition of the mind, understanding is

simply the following process:

a. organize incoming data into data-structures that the brain is

capable of storing and processing (itself a brain-process),

b. process these data structures (computation) to make

"predictions" (just more data),

c. compare these predictions with more incoming feeds from our

senses (experiment/testing),

d. and finally re-adjust the organization of data in our brain

(data-structures) to accommodate the differences in prediction data

and sensory data.

The above process continues iteratively, thus the iterative

refinements in our theories of reality, aka physics.

3. Our sensory perceptions

The data that comes in to the brain. This clearly depends on the

instruments of perception (senses) themselves. For example a person

born with a microscope attached to his eyes will transfer very

different data to the brain than most of us, and thus may have a very

different "understanding of reality".

In other words, our understanding of reality depends on brains and our

senses. It can never be any more "real" or "imaginary".

[SPK]

> we have to come up with an

> explanation of how it is that our individual experiences of a world seem to

> be confined to sharp valuations and the appearance of property definiteness.

response:

This is simply because of the similar constitution of our sensory

organs and brains (closeness in genotype and therefore phenotype if

you may). A fly's understanding of reality is probably very very

different (may or may not be sharp)

[SPK]

> What does this have to do with mathematics and models? If we are going

> to create/discover models of what we can all agree is sharp and definite-

> our physical world, we must be sure that our models agree with each other.

> This, of course, assumes that there is some connection between abstract and

> concrete aspect of *reality*.

response:

If we presume to take my above description of the nature of mental

models (mathematical/physical/etc.) as physical reality, then physical

reality itself guarantees that our models will always depend on not

only "objective reality" but also the "nature of our mind" and our

"sensory perceptions", which themselves form a subset of reality.

It is much easier to make other humans "understand" (have their brains

recalibrated to) a new model or theory than to attempt the same with a

fly (unless the fly is given a human brain and human sensory organs).

Thus this "agreement" is NOT a certificate of validity for our models.

But this does NOT imply that there is no connection between abstract

and physical "reality".

Abstract reality is a "parallel universe" created by extrapolation on

a very limited (finite?) subset of "concrete reality", namely our

brain, sensory perceptions and the computations therein. The purpose

of creating and refining this "abstract reality" (aka

mathematical/physical models) is to recalibrate the brain and senses

so that the abstract models it can hold predict incoming data

(concrete reality) with increasing accuracy.

Yet this accuracy itself is limited by laws like those given by QM

(that limits the power of our senses). This suggests that we are close

to the best we can do, although we may continue coming monotonically

closer to the asymptotic optimum that we are limited to.

--

Aditya Varun Chadha

adi...@gmail.com

________________________________

Mobile: +91 98 400 76411

Home: +91 11 2431 4486

________________________________

Room #1034, Cauvery Hostel

Indian Institute of Technology, Madras

Chennai - 600 036

India

________________________________

Jul 24, 2005, 11:13:21 AM7/24/05

to everyth...@eskimo.com

Brent Meeker writes:

> Here's my $0.02. We can only base our knowledge on our experience

> and we don't experience *reality*, we just have certain

> experiences and we create a model that describes them and

> predicts them. Using this model to predict or describe usually

> involves some calculations and interpretation of the calculation

> in terms of the model. The relation of the model to reality, if

> it's a good one, is it gives us the right answer, i.e. it

> predicts accurately. Their are other criteria for a good model

> too, such as fitting in with other models we have; but prediction

> is the main standard.

> Here's my $0.02. We can only base our knowledge on our experience

> and we don't experience *reality*, we just have certain

> experiences and we create a model that describes them and

> predicts them. Using this model to predict or describe usually

> involves some calculations and interpretation of the calculation

> in terms of the model. The relation of the model to reality, if

> it's a good one, is it gives us the right answer, i.e. it

> predicts accurately. Their are other criteria for a good model

> too, such as fitting in with other models we have; but prediction

> is the main standard.

This makes sense but you need another element as well. This shows up

most explicitly in Bayesian reasoning models, but it is implicit in

others as well. That is the assumption of priors.

When you observe evidence and construct your models, you need some

basis for choosing one model over another. In general, you can create

an infinite number of possible models to match any finite amount of

evidence. It's even worse when you consider that the evidence is noisy

and ambiguous. This choice requires prior assumptions, independent of the

evidence, about which models are inherently more likely to be true or not.

This implies that at some level, mathematics and logic has to come before

reality. That is the only way we can have prior beliefs about the models.

Whether it is the specific Universal Priori (1/2^n) that I have been

describing or some other one, you can't get away without having one.

> So in my view, mathematics and theorems

> about computer science are just models too, albeit more abstract

> ones. Persis Diaconsis says, "Statistics is just the physics of

> numbers." I have a similar view of all mathematics, e.g.

> arithmetic is just the physics of counting.

I don't think this works, for the reasons I have just explained.

Mathematics and logic are more than models of reality. They are

pre-existent and guide us in evaluating the many possible models of

reality which exist.

Hal Finney

Jul 24, 2005, 7:50:58 PM7/24/05

to cha...@bigpond.net.au, everyth...@eskimo.com

On Sat, Jul 23, 2005 at 06:09:39PM +1000, cha...@bigpond.net.au wrote:

>

> On that note I'm not sure Wheeler's description is the same. In my idea of the calculus all there is is the sheets of paper. There are no symbols (no intrinsic representation). There are intrinsic rules of formation and transformation that relate and associate the bits of paper. If the bits of paper were jigsaw pieces with implicit connective rules then it is more like my idea.

>

> If you try an build a universe as a monism from an enormous quantity of only one thing (a primitive sign - piles of little bits of paper :) ) then you can construct space and the leftovers become the stuff we call matter. Deep down it's all the one thing, however. It's been a fascinating mental exercise for me.

>

> The problem is to let go of all the maths in a symbolic sense. We have this huge and very historically justified tendency to think the linear maths is the 'real stuff' of the natural world. I have been able to think of ways in which that is not the case, but that look 'as if' it was. It doesn't invalidate our maths, it just makes it look like it's not justified to ascribe anything more to the existence of our maths than that of a useful limited description.

>

> The main thing is to get used to the idea of ridding your preconceptions of symbolic 'aboutness'. There is no intrinsically meaningful sign. However an intrinsic event: the expression of the sign (any sign), can literally be a truth in itself. The fact of the utterance of the sign itself is a truth. From that all other truths can be expressed through meaningless signs combining through intrinsic properties (affinities) for other signs.

>

> It's more like a reified mega-dimensional cellular automata, actually. Not a traditional computational one. It took me a long time to be able to let go of my symbolic mathematical tendencies when I needed to.

>

> You can make our universe out of hierarchically structured noise starting from nothing. The 'sign' in the calculus is basically the elemental noise event of the entropy calculus I have played with. Stuff that looks like the rules of quantum mechanics appears well up the hirearchy. Waaaaaay up the hierarchy it looks ontological but with structure all the way down to the elemental signs. The one that makes us is somewhere between 15? and 40? organisational layers deep. Very busy, these Leibniz's !!

>

> Lots of fun! Don't know what to make of it but at least it has enabled me to post to this thread with a little bit of novelty!

>

> cheers

>

> colin

>

>

> On that note I'm not sure Wheeler's description is the same. In my idea of the calculus all there is is the sheets of paper. There are no symbols (no intrinsic representation). There are intrinsic rules of formation and transformation that relate and associate the bits of paper. If the bits of paper were jigsaw pieces with implicit connective rules then it is more like my idea.

>

> If you try an build a universe as a monism from an enormous quantity of only one thing (a primitive sign - piles of little bits of paper :) ) then you can construct space and the leftovers become the stuff we call matter. Deep down it's all the one thing, however. It's been a fascinating mental exercise for me.

>

> The problem is to let go of all the maths in a symbolic sense. We have this huge and very historically justified tendency to think the linear maths is the 'real stuff' of the natural world. I have been able to think of ways in which that is not the case, but that look 'as if' it was. It doesn't invalidate our maths, it just makes it look like it's not justified to ascribe anything more to the existence of our maths than that of a useful limited description.

>

> The main thing is to get used to the idea of ridding your preconceptions of symbolic 'aboutness'. There is no intrinsically meaningful sign. However an intrinsic event: the expression of the sign (any sign), can literally be a truth in itself. The fact of the utterance of the sign itself is a truth. From that all other truths can be expressed through meaningless signs combining through intrinsic properties (affinities) for other signs.

>

> It's more like a reified mega-dimensional cellular automata, actually. Not a traditional computational one. It took me a long time to be able to let go of my symbolic mathematical tendencies when I needed to.

>

> You can make our universe out of hierarchically structured noise starting from nothing. The 'sign' in the calculus is basically the elemental noise event of the entropy calculus I have played with. Stuff that looks like the rules of quantum mechanics appears well up the hirearchy. Waaaaaay up the hierarchy it looks ontological but with structure all the way down to the elemental signs. The one that makes us is somewhere between 15? and 40? organisational layers deep. Very busy, these Leibniz's !!

>

> Lots of fun! Don't know what to make of it but at least it has enabled me to post to this thread with a little bit of novelty!

>

> cheers

>

> colin

>

Hi Colin, Have you written up your "entropy calculus" in a paper, so

we could have a more detailed look at it? I know you sent me a paper

of yours recently (and apologies - I haven't read your latest draft

yet either :( ), but it doesn't seem to connect with what you are

saying here.

Cheers

--

*PS: A number of people ask me about the attachment to my email, which

is of type "application/pgp-signature". Don't worry, it is not a

virus. It is an electronic signature, that may be used to verify this

email came from me if you have PGP or GPG installed. Otherwise, you

may safely ignore this attachment.

----------------------------------------------------------------------------

A/Prof Russell Standish Phone 8308 3119 (mobile)

Mathematics 0425 253119 (")

UNSW SYDNEY 2052 R.Sta...@unsw.edu.au

Australia http://parallel.hpc.unsw.edu.au/rks

International prefix +612, Interstate prefix 02

----------------------------------------------------------------------------

Jul 24, 2005, 8:40:14 PM7/24/05

to everyth...@eskimo.com

Hi Aditya,

I do not see anything in your reasoning that I would disagree with. ;-)

It seems that you subscribe to a concrete interpretation of mathematics,

which is one that I take on occasion. I merely wish to comprehend the ideas

of those that take a Pythagorean approach to mathematics; e.g. that

Mathematics is "more real" than the physical world - "All is number".

One thing that I have learned in my study of philosophy is that no

single finite model of reality can be complete. Perhaps that asymptotic

optimum involves the comprehension of how such a disparate set of models can

obtain in the first place.

Kindest regards,

Stephen

----- Original Message -----

From: "Aditya Varun Chadha" <adi...@gmail.com>

To: <everyth...@eskimo.com>

Sent: Sunday, July 24, 2005 2:20 AM

Subject: Re: what relation do mathematical models have with reality?

snip

Jul 24, 2005, 10:29:59 PM7/24/05