Keijo Ruohonen

The ability of ordinary differential equations (ODEs) to simulate discrete machines with a universal computing power indicates a new source of difficulties for event detection problems. Indeed, nearly any kind of event detection is algorithmi- cally undecidable for infinite or finite half-open time intervals, and explicitly given “well-behaved” ODEs (see [18]). Practical event detection, however, usually takes place on finite closed time intervals. In this paper the undecidability of general event detection is extended to such intervals. On the other hand, on finite closed time in- tervals event detection in a certain approximate sense is quite generally decidable, which partly saves the case for practicable event detection. The capability of simulat- ing universal Turing machines is still there, and is used to give complexity lower bounds in terms of accuracy of event detection. The ODEs used here are of course quite complicated, but not artificial, in that even from the point of view of practical event detection it would appear difficult to find criteria to exclude them.