Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!uwvax!rhesus!uwmacc!uwmcsd1!uwm-cs!litow
From: litow@uwm-cs.UUCP (Dr. B. Litow)
Newsgroups: sci.philosophy.tech
Subject: Re: Complexity and Philosophy
Message-ID: <634@uwm-cs.UUCP>
Date: Sat, 30-May-87 08:38:11 EDT
Article-I.D.: uwm-cs.634
Posted: Sat May 30 08:38:11 1987
Date-Received: Sun, 31-May-87 20:36:56 EDT
References: <19071@ucbvax.BERKELEY.EDU> <8705291501.AA12310@brahms.Berkeley.EDU>
Organization: U of Wi-Milw, College of Engineering
Lines: 38
Summary: Church's Thesis and spin glass


  An example: even though physics might be
> boiled down to automata theory some day, I fail to see how "time" would
> mean anything to such low-level calculations.  If wave-function collapse
> or what have you is an exponentially hard, or even non-recursive computa-
> tion--that seems perfectly reasonable to me.  We need never notice, be-
> cause of renormalization.
> 
> Or are you proposing a computational complexity implementation of Occam's
> razor?
> 
> ucbvax!brahms!weemba	Matthew P Wiener/Brahms Gang/Berkeley CA 94720

I doubt very much that physics is reducible to automaton theory because I
do not believe that automaton theory is reducible to itself. By that I 
only mean that we cannot understand automata behaviors in a purely
combinatorial way. The wave function collapsing mentioned in a previous
posting (included above in part) is apparently widely believed but in
'secret'. Because of the way in which I define computer science this notion
is disturbing to me. I should say that I 'sort of' believe it. CS is the
working out,largely mathematically as in physics,of the consequences of
assuming Church's Thesis. If some cooperative quantum effect e.g. spin
glasses can really be used to solve problems in,say PTIME,which have been
shown (some day) not to be in PTIME,then CT is called into question. Now
one objects that these 'damn fast' computations hold only over a finite range
of data sizes but I think that there may be theorems of CS which could
extend 'damn fast' computations over all sizes. 

I know this is vague and I am not sure that even I would agree with
everything written here. Only it is important to grasp how little is
known about computing. I would suggest also that recent work in
dynamical systems points to a severe problem in computability of
approximations to D.E.s. It would seem that even qualitative features i.e.
'...there is a gap in the spectrum in two places though we can't compute
the bands...' may not be reliably predictable before the fact because
there can be (under CT) no computable a priori estimation of the error.
Inability to use D.E.s to do such prediction runs exactly counter to
Newton's (and before him Galileo,Descartes,Kepler) mathematization of Nature.