mckee@corwin.ccs.northeastern.EDU (George McKee) (07/24/88)
Date: Sun, 17 Jul 88 11:23 EDT From: George McKee <mckee%corwin.ccs.northeastern.edu@RELAY.CS.NET> To: ailist@mc.lcs.mit.edu Subject: lim(facts about the world) -> ding an sich ? In AIList Digest v7 #41 John McCarthy wrote > There is no reason to expect a mathematical theorem about > cellular automata in general or the Life cellular automaton > in particular that says that a physicist program will be able > to discover the fundamental physics of its world is the > Life cellular automaton. This may be true if one thinks in terms of cellular automata, but if one thinks in other terms that are convertible to statements about automata, say the lambda calculus, the possible existence of such a theorem is not such a far-fetched idea. I'm enough of a newcomer to this kind of thinking myself that I won't pretend to understand this in exhaustive detail, but the concepts seem to fit together well enough at low resolution... One of the most fascinating results to come out of work in denotational semantics is that one can look at the sequence of statements that represent each step in the evaluation of lambda expressions and see that not only do the steps follow in a way that makes it proper to say that the expressions are related by a partial order, but that this partial order has enough additional structure that it can be called a continuous lattice, where the definition of "continuous" is closely related to the definition that topologists use to describe more familiar sorts of mathematical things, like surfaces in space. How close "closely related" has to be in order to be convincing is unclear to me at this time. It's this property of continuity that makes people much more comfortable with calling the lambda calculus a "calculus" than they used to be, and forms the basis for the rest of this argument. (Duke Briscoe's remarks in v8 #2 suggest that he may be thinking along these lines as well.) It means that a reasoning system based on the lambda calculus is halfway to being able to model real systems. Without going into quantum mechanics, which would lead to a discussion of a different aspect of computability, real systems in addition to being continuous, are also dense. That is, given an appropriate definition of "nearby", it's always possible to find or generate a new element between any two nearby elements. In this sense, real systems contain an infinite amount of detail. The real numbers, of course, contain infinite numbers of values like pi or the square root of 2, that fail to be computable functions in the sense that they can only be fully actualized by nonterminating computations. But a system like the lambda calculus that is able to evaluate data as programs doesn't have to compute forever in order to be able to claim to know about irrational numbers. Such a system can represent dense structures even though the representational system itself may not be dense. The issue of density is not so important in a cellular automaton universe as it is in our own, where at human scales of measurement the world is in fact dense, and a physics of partial differential equations based on real numbers has been marvelously successful. Things become really interesting when one considers a device made of dense physical material, functioning as a digital, non-dense computer system, attempting to discover and represent its own structure. The device, at the physical level, is itself, a ding an sich. At the representational level, a finite representation can exist that is not the ding an sich, but can approximate its behavior and explain its structure to whatever degree of accuracy and detail you want, given enough time. Can a device (or evolutionary series of devices) that starts out without a representation of the world devise a series of progressively more accurate representations? As long as the structure of the world (the ding an sich, not the (tentative) representation) is consistent from time to time and place to place, I can't see why not. After all, this is just an abstract, semantical way of looking at learning. But what about the last step, recognizing the convergence of the series of world-models and representing the limit of that series, i.e. representing *the* ding an sich rather than a set of approximations? The properties of continuity and density in the lambda calculus suggest that enough analogies with the differential calculus might exist to make this plausible, and that farther on, a sufficiently self-referential analog computer (the human brain may be one of this type) might be able to "compile" the representation back into a form suitable for direct action. My knowledge of either kind of calculus is not deep enough to allow me to do much more than guess about how to express this rigorously. In other words, even though it may not be possible to duplicate the universe in calculo (why bother, when the world is there to be examined?), it seems to me that it's likely to be possible to _understand_ its principles of organization, no matter how discrete your logic is. Acting congruently with that understanding is a different question. - George McKee NU Computer Science