Xref: utzoo comp.ai:5263 talk.philosophy.misc:3349 sci.philosophy.tech:1810 Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!aplcen!uakari.primate.wisc.edu!brutus.cs.uiuc.edu!apple!amdahl!kp From: kp@uts.amdahl.com (Ken Presting) Newsgroups: comp.ai,talk.philosophy.misc,sci.philosophy.tech Subject: Re: Can Machines Think? Summary: Chaotic systems cannot be modeled well Message-ID: Date: 21 Dec 89 18:31:23 GMT References: <31821@iuvax.cs.indiana.edu> Reply-To: kp@amdahl.uts.amdahl.com (Ken Presting) Organization: Amdahl Corporation, Sunnyvale CA Lines: 71 Keywords: In article <31945@iuvax.cs.indiana.edu> dave@cogsci.indiana.edu (David Chalmers) writes: >The other slightly contentious premise is the one that states that computers >can capture any causal structure whatsoever. This, I take it, is the true >import of the Church-Turing Thesis -- in fact, when I look at a Turing >Machine, I see nothing so much as a formalization of the notion of causal >system. . . . > . . . Some people will argue against this premise, saying that >computers cannot model certain processes which are inherently "analog". I've >never seen the slightest evidence for this, and I'm yet to see an example of >such a process. (The multi-body problem, by the way, is not a good example -- >lack of a closed-form solution does not imply the impossibility of a >computational model.) Of course, we may need to model processes at a low, >non-superficial level, but this is not a problem. What makes the multi-body problem a counter-example is not just the fact that the problem has no closed-form solution, but the chaotic nature of the mechanical system. In a chaotic system, an arbitrarily small change in initial conditions will over time produce an arbitrarily *large* difference in subsequent states. It is true that for any physical system, a numerical solution of the differential equations can generate a prediction of the future state with an error as small as desired. But if a numeric model of a physical system is to run in real time (as needed for the Turing test), or just proportional to real time, then there will be a fixed minimum error in the transitions from state to state. The error may be reduced by using faster processors or faster algorithms, but for a given combination of processor, algorithm, and lag behind real-time, there must be a limit on the number of terms evaluated, and a minimum error. So at the end of the first time slice, there will be a finite difference between the state of the real system and the calculated state of the model. The real system will proceed chaotically (as will the model), to amplify the discrepancy in initial state and each subsequent state until (sooner or later) the real system will be in a state which diverges from the state of the model by any amount (up to the size of the system). That was a rough sketch of a proof that not all causal systems can be modeled by programs. Let me add a plausibility argument, so that the claim will not seem counter-intuitive. What makes the analog causal system different from the algorithm is that each state of the analog system encodes an infinite amount of information. This holds even for electrons bound into the quantum orbitals of an atom. There is a finite number of electrons, and transitions between levels are discrete, but there are infininitely many energy levels (most of them very close together). Of course, a processor has finitely many states, and encodes a finite amount of information. In addition, an analog system need not time-slice its calculations. It can make infinitely many transitions in any interval. A Turing machine would need to have both infinitely many states and run arbitrarily fast to prescisely match an analog system using a numerical algorithm. Now, the lack of precision is insignificant for many analog systems in many applications, where the error is constant or grows slowly. But in a chaotic system, the error in the model can grow very rapidly. If the numerical model cannot be allowed to lag arbitrarily far behind real-time (thus trading time for memory) then the amplification of error will make the model useless. The "solutions in closed form" of rational mechanics gurantee that that a numerical model for an analog system will have a rapidly computable algorithm (often a polynomial). So the fact that the multi-body problem has no solution in closed form is relevant, but that's not the whole story. More important is chaotic amplification of initial differences. This does *not* show that strong AI is impossible with algorithms. There is no way to know whether intelligence requires chaos. But the brain is certainly complicated enough to be as chaotic as fluid flow. Modeling human behavior may well have to deal with this problem. BTW, I'd like to know if anyone has heard this kind of argument before in connection with AI. It must be old hat in simulation circles.