is induction unformalizable?

599 views
Skip to first unread message

Wei Dai

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

Ben Goertzel

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

Ben Goertzel

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

Wei Dai

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

Ben Goertzel

unread,
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
-----Original Message-----
From: Wei Dai [mailto:wei...@weidai.com]

Hal Finney

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

> 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

Bruno Marchal

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


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

Hal Finney

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

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

scerir

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

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


Bruno Marchal

unread,
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/


Wei Dai

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

Hal Finney

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

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

Stephen Paul King

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

Brent Meeker

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

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


Stephen Paul King

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

Brent Meeker

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


cha...@bigpond.net.au

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


Hal Finney

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

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

cha...@bigpond.net.au

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

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


Stephen Paul King

unread,
Jul 23, 2005, 9:57:05 PM7/23/05
to everyth...@eskimo.com
Hi Brent,

----- Original Message -----
From: "Brent Meeker" <meek...@rain.org>
To: <everyth...@eskimo.com>
Sent: Friday, July 22, 2005 8:31 PM
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

Brent Meeker

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

Aditya Varun Chadha

unread,
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
________________________________

Hal Finney

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

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

Russell Standish

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

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

Stephen Paul King

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

Hal Finney

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