🚀 go-pugleaf

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.