Stephen Paul King (firstname.lastname@example.org)
Tue, 23 Nov 1999 16:01:46 -0500
Colloquium on Reasoning about Actions and Change
The fire was burning: now it is out. What happens at the boundary instant dividing these two successive states? Is the fire burning or not at the dividing instant? We seem to have no good reason for preferring either, which means that we must either choose both - incurring a contradiction - or neither, incurring a truth value gap. To dramatize the matter, think of the instant of death. I am alive now, I will be dead sometime later. There must be a boundary point between these two states, as both common sense and major novelists tell us. But, is that boundary point the last moment of my life, or the first moment of my state of death? Or are things even more mysterious than that, and are there contradictory, or incomplete states of being in addition to just being alive or dead? (Indeterminacy may be a reality in some countries. When Einstein was considering a move to Leiden University in Holland, the famous physicist Ehrenfest tried to dissuade him from the move, by telling him that the Dutch university professor is the only species on this planet where the distinction between life and death is completely undetectable.)
Ancient historical problems like the Dividing Instant (henceforth: 'DI') can trigger contemporary debates. All through this spring and summer, there was a lively discussion on the structure of time and temporal modelling in the electronic newsletter on "Reasoning about Action and Change" (http://www.ida.liu.se/ext/etai/actions/njl/) sparked off by DI. Contributors were Peter Grünwald, Pat Hayes, Jixing Ma, Ray Reiter, Erik Sandewall, John McCarthy and others. The result was a wide-ranging exchange of views, sometimes resembling a soap opera, with gradually multiplying story-lines, interludes of bad spirits, and periodic commercial breaks where participants advertised their own systems. At the request of ENRAC editor Erik Sandewall, I am putting in my penny's worth. It will not be a grand resolution of the dispute, but one logician's view - no doubt, controversial. (Erik's first informal reaction has already made that clear... But I won't complicate matters by addressing all possible reasonable objections at this stage.) In particular, I perversely intend to introduce further complexities, rather than simplifications! This reflects my conviction that many issues raised in the DI debate just have no unique solution. One must sometimes have the courage to choose.
The first thing that struck me is how the debate raised old philosophical questions, that come up again and again. It is as if serious investigators exploring the structure of time just have to pass by these great landmarks. For instance, the puzzle of the Dividing Instant for a fire that went out goes back to the Middle Ages. And as with many famous philosophical problems, it is not entirely clear what the problem is! We are forced to first clarify our thoughts, and then see what solutions exist to what versions of the problem. In my preferred reading, DI is an issue about interfacing two kinds of language. Does talk which makes sense at a durational phenomenological level - where we see that fires are burning, or are out - extend to underlying invisible durationless 'turning points' supplied by some mathematical model of the continuum? In addition to such perennial philosophical problems, the ENRAC debate also showed recurring differences in methodological stances - which I will discuss later on. Before doing so, let's go back to Antiquity for more perspective on our discussion. Zeno's famous Paradox of the Arrow contrasts the following observations. A moving arrow moves along all points of its trajectory. And yet, at each of these durationless points, it has no time to move: and hence it stands still 'all the time'. Zeno and the Eleatics took these conflicting outcomes to mean that time is inherently contradictory, which fitted their philosophy of the True World as one unchanging whole. The contradictory nature of our intuitions concerning time has been a persistent theme in philosophy ever since. Famous examples are Kant's 'Antinomies of Pure Reason', one of which concens the boundaries of time, or McTaggart's argument in this century concerning 'The Unreality of Time' which triggered Prior's tense logic. It is extremely interesting to see similar issues come up AD 1998 in the practical setting of reasoning about action and change.
My own view is that these paradoxes have a common source. They conflate different views of temporal structure, and argue as if the same predicates meaningfully apply to both. E.g., "moving" is a predicate which applies meaningfully to objects over extended temporal entities: let's say, intervals. These are the primary objects of observation - and of learning by children. Later on, we develop a new underlying mathematical conception of a continuum of durationless instants or points (this is an abstraction, as nobody can observe these) out of which these intervals are 'composed'. Then, we ask if the object "moves" at some such durationless point. This makes no sense without first stretching the original predicate, because it just has no natural meaning for these new-fangled temporal objects. In general, the old predicate may not make any reasonable sense at all! My own feeling is that none of the usual descriptive predicates in natural language, including those purporting to report 'instantaneous' events ("reaching the top") or states ("being in love") make direct intuitive sense on temporal points. Just try!
The latter insight often tends to get obscured, for two reasons. First, we are taught 'point talk' in school, say in physics classes, in a non-reflective manner which suggests that there is no problem whatsoever. Balls hit walls and bounce back instantaneously, etcetera. This talk is all right as long as it does not lead to problems. But it is really no more than a choice for one particular mathematical model of time, which does not sit too happily with intuition. (Try to imagine any collision of a ball and the wall: there just is no meaningful durationless turning point...) Now, it is true that something more systematic can be said. There are indeed cases where some natural extended meaning can be constructed for points, not by nature, but by us. Thus we might say that
an object "moves" at point |
This is a well-known semantic recipe for defining a 'progressive tense' over points. But please note that such a move is not a license for carefree 'point talk'. For, any meaning extension has systematic consequences. Take this particular example. Assume simple logical bivalence for intervals i : either "move"(i) or not-"move"(i). This induces at least three possibilities for points t : (1) some "move" interval i contains t, but no non-"move" intervals do, (2) some non-"move" interval i contains t, but no "move" intervals do, (3) both types of containment occur, and perhaps (4) no such containment occurs (when t is outside of any interval). What this illustrates is that any meaning extension will induce more than two natural types of point behaviour, so that simple bivalent classifications from the interval level must be dropped. This remains true when we start from interval predicates "move" and "rest" (both: throughout), enforcing temporal disjointness of their respective intervals - leaving a third natural kind of 'transitional' intervals that intuitively lack both properties. By the above stipulation, a point can then be inside a move interval, or a rest interval (the above case (3) is excluded), or it only sits in transitional intervals, meaning that the point is a boundary between extended movement and extended rest. There is absolutely nothing contradictory to this description - and making such distinctions will make Zeno's Arrow Paradox go away.
There are other transfer conventions for predicates from intervals to
points than our simple 'progressive'. For instance, physical "instantaneous
velocity" is a different, and more sophisticated way of transferring
macro-notions to micro-notions. And even in 'common sense physics' transfer
variety occurs, witness well-known verb classifications in linguistics. The
above convention is plausible for 'activity-predicates' like "moving" or
state-predicates like "being alive". But, e.g., 'accomplishment predicates'
like "reach the top" do not have such a simple transfer. I do not plausibly
'reach the top' at a point
Philosophical problems are often brief, stated in ordinary language, which suggests the issue raised is clear. But that simple formulation may hide tricky presuppositions, which only come out in logical analysis. One reason why the paradoxes have been with us since Antiquity is precisely this possibility of constant reinterpretation of the issues. In particular, specifying the DI problem requires two stages, one 'ontological', one 'logical': (1) Which temporal objects are involved and with what structure?, (2) What conditions must the resulting temporal models satisfy? Thus, we can have DI versions over points, or over intervals, or over both. In each, we may or may not have 'boundary problems', depending on the further conditions assumed for these objects.
At this stage, some readers may get exasperated. Why all this abstract verbosity, why not give a short answer to a short problem? Well, I for one, do not think that the DI 'problem' is clear at all. Just for starters: what is "the boundary instant"? Not every definite description which we can write down in natural language is bound to have a sensible denotation. Why should all transitions between neighbouring temporal entities include such a thing? The 'boundary instant' will only appear as a result of assumptions.
To make multiplicity even worse, the specification of the problem itself can take different legitimate forms. (The following methodological difference came up in the ENRAC discussion.) One excellent approach is to give the 'simlarity type' of the temporal objects via a formal language, and then state axioms, or whatever format of principles defining the temporal reasoning allowed. The intended temporal structures can then be taken to be all models of these axioms (whether standard or non-standard, intended or unintended). This is the axiomatic approach, which has a long pedigree in mathematics and logic (think of geometry or algebra). In computational practice, specifying the admissible principles of reasoning is the best one can do (unless one works with finite structures which admit of direct model checking).
But there is also another ubiquitous approach in mathematics and logic. One can start from some unique temporal model, or perhaps a class of such models, as the intended structures. This is like defining 'Analysis', not as a particular axiomatic theory, but as the study of the real numbers, or similar intended structures. Both methods have advantages and drawbacks, also for the case of temporal reasoning. In practice, one often finds them, not as rivals, but working together. Intended models suggest (not necessarily complete) axiomatic theories, while such axiomatic theories, in their turn, suggest useful new models... In temporal logic, the main trend has been to start with specific models, such as the real numbers, branching trees, or Minkowski space-time. But the same 'methodological spiral' occurs. E.g., Minkowski space-time suggests interesting axiomatic causal theories, which then turn out to have quite new models.
Let's imagine one more irate reader. "Logician's hocus-pocus: all this talk about different 'temporal models'. We know what we mean. We are talking about Real Time, of which there is just one." Well, good luck. Real Time is as elusive as The Continuum or Real Space, and mathematics in this century tells us that these items are problematic. (If "IR" were really such an evident structure, why has nobody settled the Continuum Hypothesis?) A Platonist may believe they exist, but she has to admit that our intuition seems inadequate for perceiving even simple truths about infinite mathematical objects. A constructivist says that we create these objects as we theorize, and hence they reflect what axioms we first put in there (plus their distal consequences). If there were a vigorous intuition of Time shared by all of us, we might resolve our disputes by walking to it, and reading off the answer. But there is not, and the moral of problems like DI lies precisely in their role as a focus for ontological construction and decision.
I can see two versions of the DI reasoning. 'Homogeneous' versions have just one kind of temporal entities, say, intervals or points. With intervals, I fail to see any problem whatsoever. I can imagine any kind of immediate neighbour situation for two intervals "burn" - "out", with or without 'boundary intervals'. Moreover, intervals fall naturally into three (not two) kinds: "burn", "out", "neither" (the latter is natural for transitional intervals). If there happens to be a boundary interval, I'd probably classify it as the latter. But the point is that there is no contradiction: you as a specifier must decide what you want. State if you want boundary intervals to exist, and if they do, you can still take different decisions on different boundaries in one model - and across models. Of course, if you fix an intended interval structure rather than an axiom set - say, all open real intervals - then the existence issue will be settled for you: but the second kind of freedom remains. Next, with just durationless points, you have to stipulate very carefully anyway what you mean by saying that a predicate "burn" holds at a point. This was the point of my earlier discussion. After that, you will have your answer for the dividing point - if one exists. (Not all point structures enforce this...) In particular, the latter would be my answer to no-nonsense people who say "Time = Real Numbers", "DI = Dedekind Continuity of <". Please state your definitions for the temporal predicates "burn", "out" at points (no natural intuition suggests itself to me), and all will be revealed for the boundary: "burn", "out" or "neither". There is no truth of the matter to be discovered, until you yourself are clear about what you mean.
To me the deeper version of DI interfaces two kinds of temporal entity. Predicates like "burn", "out" are evidently phenomenological, presupposing duration. They make no sense at durationless points, only at extended intervals. The latter are of three kinds, as we have seen: the fire may be burning, it may be out, or we have neither, because both phases occur over the interval. So far, all is well. Now someone claims there is a boundary point at which "burn", "out" meet, and where we "have a problem". This takes some analysis. In the heterogeneous case, the boundary point lies in another realm than the initial intervals. This is by no means an esotherical event. We often divide our ontology into different levels: as with physical macro-objects versus atoms. In general, in this process, we will not assume that the same predicates apply to both. Your eyes have a colour, their composing atoms do not. And vice versa, predicates which make sense for atoms need not make sense for eyes. What we assume at best is some kind of correlation between predicates at the two levels, but what this correlation is may be hard to formulate. In this light, our earlier attempts at transplanting interval predicates to temporal points (as a way of reconstructing hte 'DI problem') may have been naive. At best, we can try to see if there are correlated predicates, which may be definable in terms of those at the intervals, but need not be. For instance, the 'progressive' schema of Section 4 above might serve in many cases: but we have pointed out its limitations.
But a case may be made for a more intimate connection between intervals and points. Are not points entities that are bound to arise by some canonical construction out of intervals? (Think of the Russell-Wiener construction, or its many later variants.) Such constructions enforce a temporal precedence structure on these points, derived directly from the precedence/inclusion structure of the original intervals. So, why not have a similar derived meaning for predicates like "burn" or "out"? Well, the analogy is not clear. No obvious uniform definition schema will work for 'historical predicates' over the temporal base structure (this is shown in my book "The Logic of Time"). But even if we have somehow arranged this, the main point is this. Suppose that we fix (a) any construction, plus (b) a transfer convention for interval predicates to points. Moreover, suppose that a dividing instant arises. (Again, as shown in "The Logic of Time", not all point constructions have this effect: some supply end-points for the burning and initial points for the out-periods.) Then, the assumed convention (b) will tell us without contradiction what the dividing instant does. Of course, we can construct our intuitive agnosticism about DI between "burn" and "out" as a preference for those conventions that do not give it either status. More radically, we may also construe it as an argument against the whole 'lifting' enterprise for predicates from intervals to points.
On the whole, every analysis which we have given makes it a somewhat conventional matter which status is accorded to DI (if any). This is by no means a policy of despair. In natural language, we are quite used to predicates having a determinate range of applicability, outside of which matters become blurred. (Think of vague predicate like "young", or "bald", which can only be made more precise by somewhat arbitrary fiat, doing injustice to 'boundary cases'.) Why would one expect more precision here?
One strand in the ENRAC discussion was the issue whether there are principled preferences for modelling time with intervals rather than with points. This was more of a burning issue in the seventies. No definite answer has emerged, as far as I can see. Philosophically, one can certainly defend a preference for intervals, as our primary intuition of time seems to involve 'extended chunks'. On the other hand, through education these intuitions quickly become tutored, and many people have no problem with recognizing the non-extended instant at which a bullet reaches the highest point in its trajectory as a legitimate household object. (At least, as longs as you do not try to imagine what really happens there...) Linguistically, there have been many arguments in favour of basing natural language semantics on intervals, rather than points. But in that area, temporal semantics has become much more sophisticated than this simple statement would suggest. For instance, in contemporary work on temporal discourse representation, one works with sequences of growing interval models, where at each stage, the atomic intervals have a sort of point-like status. But this is temporary, as they may always be refined at later stages of discourse. Thus, static views of temporal structure have become more dynamic. Finally, computationally it has been claimed that interval calculi are simpler than point-based ones. I used to believe this, but it now seems a simplification to me. It all depends on the vocabulary, and the task one considers. In general, interval structures seem richer than point structures, inviting more expressive languages, and presumably, more complex axiomatizations. But for some tasks and matching languages (like the limited algebraic combinations in Allen's Calculus), interval computation may be easier. In my experience, logic or complexity theory provide no knock-down arguments here either way.
It will be clear from all that I have said what my own view of temporal structure is. There is a hierarchy of various temporal structures, corresponding to different 'grain sizes' that we want to study. One can have intervals plus points, or days,/hours/seconds. In this richer ontology, one wants to develop a variety of temporal structures, plus a new feature: their systematic interconnections. For instance, I do not think that lifting the same predicates from one level to another is the main issue. It is often easy to find connections between mathematical ordering structure (such as precedence or inclusion) going from one level to another. But as for predicates with factual content, the general case seems to be that each level has its own natural predicates - and that we should study their connections (not necessarily: inter-definitions). Some interesting logical tools for this purpose are emerging, such as Montanari's 'switching operators' which take us across temporal levels, or Gabbay's framework for merging different logics.
Standard physics textbooks show no qualms about temporal predication at intervals or points. Observers meet at durationless points and exchange light signals. Velocities can only be measured over extended intervals, but standard velocity functions in mechanics are defined on points. I think it would be worth-while analyzing this practice more closely, and understand why it works. But also, where it works. For instance, the reason why we can define instantaneous velocity is an assumption of differentiability of the position function for a particle. In other words, this practice works only for special physical predicates showing enough 'smoothness'. Could the reason for the absence of a standard stipulation for instantaneous "burning" be the lack of a such smoothness for general logical predicates? I will not pursue this issue here, but it is suggestive. For instance, we can try to smoothen things in terms of a 'fuzzy logic' with a continuum of truth values. If the value of "burn" decreases continuously from 1 to 0, say, that of "out' will increase inversely, and we may all agree on some kind of natural interpolation at the boundary point. I leave this as a speculation. But my main point remains this. The physics method works for well-chosen smooth predicates (perhaps, that is why they are 'physical predicates'...). General predicates may be much more erratic over time.
Perhaps the preceding discussion has sounded a bit tongue-in-cheek. But my honest impression is this. Problems like DI are important, even if inconclusive, because they sharpen our thinking about time. Discussions like ENRAC's are important, because they show how academic debate can have quality and yet be interesting in real-time. I wish there were a way of importing more of this liveliness into classroom practice.
Here are some surveys of temporal logic which I have written over the years. They provide further technical background for many of the above points:
1983: The Logic of Time, Reidel, Dordrecht. (Second revised edition, 1991, Kluwer, Dordrecht.)
1989: 'Time, Logic and Computation', in J. W. de Bakker, W.-P. de Roever & G. Rozenberg, eds., Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, Springer, Berlin, 1-49.
1995: 'Temporal Logic', in D. Gabbay, C. Hoggar & J. Robinson, eds., Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 4, Oxford University Press, 241-350.
1998: 'Temporal Patterns and Modal Structure', Report CT-98-03, Institute for Logic, Language and Computation, University of Amsterdam. To appear in A. Montanari, A. Policriti & Y. Venema, eds., Amsterdam Workshop on Temporal Logic, Bulletin for Pure and Applied Logics, London.
Erik Sandewall, Linköping University, Sweden.
This debate contribution can be cited as resident at the following URL:
This archive was generated by hypermail 2.0b3 on Wed Dec 01 1999 - 01:15:40 JST