A New Kind of Science: The NKS Forum > NKS Way of Thinking > Penrose example of non-computable determinism
Author
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Penrose example of non-computable determinism

Penrose has a new book, "The road to reality", out this month. I haven't read it yet but it looks fun.

He has some slides online with bits from the book, one of which I thought might be of particular interest here. It is a toy example meant to show how a definite rule can be deterministic but formally non-computable. What I like about it is the way it serves to distinguish determinism from computational constructability, as in a sense an easier condition.

The idea is to pick next states from a constructable set according to a step by step "switch" that depends on a computationally intractable problem. The slide is here -

http://online.itp.ucsb.edu/online/p...rose/oh/14.html

An Amazon link for the actual book can be found here -

http://www.amazon.com/exec/obidos/t...=glance&s=books

Report this post to a moderator | IP: Logged

02-25-2005 05:21 PM
Vasily Shirin

Registered: Jun 2004
Posts: 78

This "definition" relies on the
axiom: "either A or not A". However, when A is intractable, the validity of this axiom is
a religious issue. Not to mention the fact
that it will take infinite time for evolution
for calculate the next state.

Apparently, the road to reality now passes through infinity.

Report this post to a moderator | IP: Logged

02-25-2005 06:59 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Sure, anyone who believes that reality is confined to constructible, computable operations (one version of Church's thesis) would regard this toy example as a physically unrealizable system. The set can be constructed and elements out of it identified readily enough, but picking which one at each step involves answering an instrinsically difficult question. What realizable "machinery" is supposed to tell the universe which way to go at the next step?

But its unrealizability does not stem from any lack of posited underlying determinism (no stochastic underlying processes etc). The example obviously can't settle anything about Church's thesis. Penrose has a well known position on that, of course, one different from Wolfram and NKS. The example still shows that determinism and computability are separable in principle, with computability a stricter requirement than determinism.

I should probably add that NKS shows predictability is another level again, since there are computables that aren't reducible i.e. that can be solved but only by direct emulation, doing all the computational work that the system itself performs as it evolves. Predictable beforehand is a proper subset of computable, computable is a (logically if not physically) proper subset (and always a subset) of determined, and determined is a proper subset of "obeys any sort of rule or law" (which e.g. QM or any similar underspecified or statistical model may do, without possessing the quality "determinism").

Report this post to a moderator | IP: Logged

02-25-2005 11:32 PM
Vasily Shirin

Registered: Jun 2004
Posts: 78

OK, what if we define another "deterministic" machine
the behaviour of which depends on how many angels
can sit on a tip of a needle at moment T? For somebody, this condition makes perfect sense.

This story reminds me novels by Lewis Carroll
or Jonathan Swift.

Report this post to a moderator | IP: Logged

02-26-2005 01:44 AM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

One of these things is not like the other. You can find all sorts of tilings and prove others can't tile - there just isn't any general way of doing all of them. Not a matter of semantics.

Report this post to a moderator | IP: Logged

02-26-2005 02:56 AM
Vasily Shirin

Registered: Jun 2004
Posts: 78

It IS a matter of semantics.
I, for one, don't understand the meaning of axiom A | !A
if A is intractable. I'm not ready to say whether it's true or false - it's as much a riddle as a question
Although, as I mentioned before, it's a religious issue,
so it's not surprising that we can't come to agreement.

Report this post to a moderator | IP: Logged

02-26-2005 03:52 AM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

But I do not require you to assign a meaning to that supposed axiom, which you brought up not me. A semantic disagreement is empty because it stems entirely from conventional assignments of meaning to chosen terms. To say that a disagreement is merely semantic is to say that those involved are attempting to enforce chosen assignments of meanings to terms upon others they are debating, instead of allowing said others to assign said meanings as each of them sees fit.

The only place one could detect a semantic disagreement in this case is over ascriptions of meaning to "determined". If you choose to assign the meaning, "constructable by a definite computable function", then sure the toy rule is not determined. But this is the meaning conventionally assigned to "computable" not to the meaning "determined". The toy case simply illustrates a way in which the two need not coincide - even if usually they do coincide, and even if everyone is free to regard mathematical cases where they do not as unrealizable in the physical universe.

And I have no idea why you call the matter "religious". I don't regard non-computables as physically realizable, while Penrose does. But this does not prevent me from seeing that he is disagreeing with me in a claim about the world, and not in a claim about the meaning of terms. You apparently agree with me that non-computables are not physically realizable. But this apparently is insufficient to result in agreement about whether to separate the usage of "determined" from the usage of "computable".

Report this post to a moderator | IP: Logged

02-26-2005 04:12 PM
Vasily Shirin

Registered: Jun 2004
Posts: 78

A | !A was brought up not by me, but by Penrose.
His construction works only if either set tiles the plane,
or it doesn't.
What is the meaning of "set tiles the plane"? Please try
to explain it to somebody - I'm sure at some point in your
explanation the notion of proof will pop up. It tiles the plane
if and only if you have a proof that it tiles the plane.
Similarly, it doesn't tile the plane if and only if you have a proof...
Sometimes, however, neither can be proved.
What will this machine do then? And, worse, what this machine
will do if someone manages to prove that for given set
neither proof exists?

Maybe, for Penrose, the meaning of statement "set tiles
the plane" has nothing to do with the notion of proof?
But what is it then? The only alternative in sight is to
conjecture some mystic realm where each statement
is ascribed a value of true/false, whereas we mere mortals
are doomed to never learn it.
But then, the whole machine should work in that mystic realm.

Report this post to a moderator | IP: Logged

02-26-2005 07:52 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Proof is not equivalent to truth. It is a much harder condition. Proof nowhere enters the definition of tiling - which could be replaced by any other hard problem incidentally, in the construction - some set of facts about arithmetic e.g.

Proof is not even equivalent to knowable - we know lots of things that are not matters of proof. Knowledge is a distinctly looser thing. All inductive results, all observation, all operational skill is outside the sphere of proof, but not of knowledge - for example.

Even knowledge is not equivalent to truth. There is no apriori requirement of truths, that they be known. All sorts of things have been unknown for eons, obviously, without ceasing to be true. Knowledge is something that certain animals occasionally achieve as a particular relation between reductive maps, not the world.

And reasonable belief isn't equivalent to knowledge. We know precious little, while our reasonable beliefs are considerably more extensive. There is no cosmic requirement that reasonable beliefs be restricted to things actually known. It is an utterly practical question, and the reasonable position with respect to it includes plenty of legitimate guesswork, provisional convictions, etc. Plenty of things have been, are, and will in the future be reasonably believed by all sorts of people, that not only aren't yet known, but that aren't even true.

Error is the natural state of mankind, not a cosmic illegality. We guess and we iterate on our guesses, and that is perfectly reasonable, since the aim is not to avoid a few narrow errors but to find any serviceable knowledge at all.

None of which really address the question of the realizability of non-computibles - they are just philosophy 101. Free minds don't need fences telling them they have to be able to prove something to think about it. It is just plain false and not helpful.

Nor does anyone think a world modeled by differential equations would need lots of little Mathematicas running inside every particle using a super NDSolve to tell it where to go. Such equations get intractable very quickly, from a computational perspective. But those who model things with them assume some simple underlying point by point evolution just arrives at the same result as a super NDSolve would.

One can think it more likely that any real physical process is readily computible, certainly, and NKS does. But not because it thinks any physicist using continuous math is a religious zealot. That would be delusional.

The perspective presented by NKS, its hunch, is that physical realities are going to be computable, and that present formalisms that lack that property will eventually be seen as good approximations to underying computable processes, or as true but not exhaustive mappings of some of their stable properties or large size limits (central limit theorem fashion, perhaps).

But NKS recognizes that this is far from an apriori requirement or part of the definition of being reasonable, and instead requires success at the quite difficult task of constructing a finite basis for fundamental physics. One can see that as a promising subject to explore, without pretending what can't be maintained - that it has already been accomplished.

NKS expects underlying determinism. But all present deterministic theories that grapple with the QM evidence underspecify the world. Determinism in an ensemble is not determinism in the world. "You will see something" isn't even a theory, it is a truism. "Drawn from this ensemble" can be a theory if the ensemble in question is restricted enough (as it generally is for experimental results) otherwise it isn't any better than the previous (and this can enter at the level of cosmology, where our sample size drops to 1). But isn't yet a determinism at the level of phenomena.

NKS also expects that unpredictability will occur even with a fully deterministic and fully computable world. That a rule is deterministic does not ensure that it is predictable. The rule updates according to its rule table or what have you - but can anyone else follow that calculation? If it isn't even computable in principle, then "no". (Which is the subject Penrose was trying to touch with his illustration).

But even if it is formally computable, the answer can still be "no". A computable evolution might be irreducible. Then sure, all you have to do is directly emulate, the problem has been reduced to logic and you can just grind it out. But reduction of a problem to logic is not equivalent to solving a problem. Enough logic, involved enough logic, is hard.

This case differs from the previous in that a general method for constructing the answer may well be known, and be implimentable. But this is still not enough to predict. It is enough to simulate or model. But prediction is a harder requirement - one needs to be able to outstrip the system's own calculation, to arrive at its outcome before it does so itself. If the system's internal calculation "wastes" a lot of "effort", then this can be done. A shortcut can get the answer of many steps in a few. We say, the internal evolution of the system is computationally reducible. Which is more than "computable", something additional on top of that.

NKS traces the - empirically seen - limited prior knowability of the world to irreducible but computable processes. Penrose wants to trace them to formally non-computable ones (which NKS suspects can't actually be implimented with physical components - while irreducible but computable processes clearly can be - we do it all the time). Many world QMers want to keep determinism only at the level of an ensemble of possible worlds, and underspecify observables. Objective chance QMers throw determinism overboard entirely.

These are perfectly rational differences in beliefs and hypotheses about difficult subjects. Reasonable people disagree about such questions, simply because they are hard, and we do not at present know the answers to them. People reasonably disagree about whether we ever will, or if so how or by what sort of evidence or reasoning, or about the level of knowledge or certainty attached to those.

Trying to forbid opinions about such matters as metaphysical thought crimes is a pose that was unjustified even when first indulged, and one that has been completely debunked in philosophic circles for several decades by now. Penrose is a reasonable man who disagrees with me. He gives me his reasons and I consider them. Nothing religious about it.

Report this post to a moderator | IP: Logged

02-27-2005 12:43 AM
janos

CT

Registered: Nov 2004
Posts: 23

It is "interesting" to see that there is no reference in NKS to "Roger Penrose" - I just did an online search -, and vice versa there is no mention of Stephen Wolfram in Roger Penrose's new book - I checked that yesterday evening. Any good explanation ? I am sure they speak to each other... sometimes.

__________________
--------------------------------------
sunflower oil, and not only bought it, but
spilled it too."
Bulgakov: Master and Margarita

Report this post to a moderator | IP: Logged

03-04-2005 07:22 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Funny you should ask. Penrose was in Cambridge yesterday to give a talk promoting his book.

I went with some others from Wolfram Research and got my copy signed. Wolfram had coffee with Penrose before the talk. It was a good talk, encouraging people that there is still lots of new physics to find, explaining his views on some recent big ideas in physics (skeptical, as readers of the book will have gathered). He also mentioned a 2003 paper by Witten that looked at combining strings and twister theory, which he was clearly pleased about.

Afterwards Penrose had his driver wait while we all had a bite in Harvard square. Not a lot of time, they talked about QM and related subjects as well as various less formal chit chat. Then Penrose had to go. Wolfram and some youngsters went to a lounge at the Charles hotel, and we stayed talking and doing real time computer experiments until they closed.

They get along fine. Different generations. Wolfram took a course with Penrose once, maybe thirty years ago now, I think it was in general relativity. Knows some of his students. For me, yesterday was the first time I'd met Penrose in person, though of course I've read his stuff. He is a charming man, lively, clearly loves ideas.

The book looks fun - substantive math and coverage of a lot of territory in physics, along with his opinions on big issues. He explained in the talk that part of the idea of the book was to avoid the distraction of contentious consciousness subjects to stick to math and physics. I've liked the parts I've read so far.

One man's opinion...

Report this post to a moderator | IP: Logged

03-05-2005 04:20 AM
Chris C

Registered: Mar 2005
Posts: 2

Real Numbers

Jason Cawley, in the post before last, objected to the use of the word, 'religious', to describe physicists' belief in continuous mathematics. I would assume those posting on this site are not religious, and the word was intended and understood as being used in the perjorative sense. I also get the impression that jason is playing devil's advocate with his objections, or just trying to calm the tone of the debate. However, I think this is actually a good analogy on many levels, and is of some use in illustrating why the majority of scientists and mathematicians do maintain a strong belief in the real number line as being very much a real object, and as natural as the natural numbers, and why a minority of enlightened NKSers do not share this belief. It is a similar situation to the position faced by atheists, and for similar reasons: If one approaches with an open mind just that fraction of human scientific knowledge that one would consider 'commonly known', the existence of a god seems highly unlikely, and the specific details added by the most popular religions, even less likely. But most people do have some sort of religious beliefs, and in fact we can identify particular features of human brain functioning (such as the feeling of sometimes being watched and judged, that even atheists get), as well as details of human culture and history, that make people likely to invent god and religion. Similarly, if you write down a set of axioms defining the continuous manifolds used in the current most popular 'Theories Of Everything' in physics (or just axiomatise the real number line, with the standard topology induced by the euclidean metric), they would appear rather contrived and unwieldly, and one would suspect that if one were to systematically probe different mathematical structures in the hope of finding the simplest one that could describe our universe, they would not be amongst the first to be tested. Nevertheless, even a child can have a strong sense of what properties a continuous line should have, so that when one finally learns a system of axioms that yields these properties, one has the feeling of atruth being revealed. However I would consider that these 'defining properties' of manifolds are seen as having a special status among mathematical objects because they coincide with rules applied by the human visual system to break up objects into regions and boundaries, and with other systems involved generating a sense of spacial awareness. For instance, the sharp and fuzzy boudaries one envisages when thinking about (topologically) open and closed sets suggest the origin of these concepts is in objects being in the foreground or background of our field of vision.
My own views on the matter are that the real number line is that they are very much a product of our imaginations, invented by man rather than by nature. A reference I would recommend for the sceptical is the reprint volume of Gregory Chaitin's papers, 'Information, Randomness and Incompleteness' from World Scientific. All the papers in it seem rather like variations on a single theme, and in some senses its content could be seen as a special case of the mathematical universality described in ANKOS. However, I believe it is a very important special case: He focuses a large amount of intellectual power on unravelling the real numer line, and it left me with the feeling that after 'computing' the natural numbers (a task many insomniacs have undertaken, with varying results), and then computing that fraction of the real numbers one could possibly compute, even using any number of different rulaes and languages with which to perform the computations, the remainder, the uncountable continuum of reals, would not really add anything new: They can in fact all be described by a single operation: Toss a coin: If heads, write a 1; if tails, a zero. Carry on forever. Any way in which such a number could affect a physical system in which it was used as a parameter would be indistinguishable from just making a random choice 'within the program' (or making both choices, if you believe in many worlds theories, which i do, for pretty much this reason: that fundamental mathematical systems are deterministic but quantum mechanics isn't). To say that there was actually a number all along that determined this outcome, but one couldn't possibly have known it, is very much a matter of faith, and in no way comparable to the physically real 'unpredictability' displayed by computationally irreducible systems which, after all, could in fact be predicted if sufficient computational muscle were applied (Even with such irreducibility in fundamental physics, one could use a large part of the universe to model a smaller one).
Regards,
Chris Collins

Report this post to a moderator | IP: Logged

03-24-2005 04:14 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us