Computability-theoretic limitations of qualitative simulation

Abstract

Qualitative reasoning and simulation are useful mathematical tools, especially for theanalysis, design and diagnosis of dynamic systems. Simulators which are seen to beincomplete, that is, which produce spurious predictions for a particular input, are usually augmented with additional filters eliminating that behaviour. Kuipers introduced asimulator (QSIM) which has the soundness property, that is, no trajectory which is thesolution of a concrete equation matching the input can be missing from the output. It hasbeen proven that there does not exist a sound and complete simulator whose input and output vocabularies are identical to those of the "pure" QSIM.This thesis contains a series of further results about computability-theoreticlimitations of qualitative simulation. Firstly, it demonstrates a method for modeling andsimulating an arbitrary Unlimited Register Machine (URM) using QSIM, and thereby establishes that qualitative simulation has universal computational power. By making useof reductions from the famous undecidable Halting Problem for computation toolspossessing universal computational power, it proves that it is impossible to build a soundand complete qualitative simulator using the QSIM representation for input and output for several "weakened" versions of the representation. It finishes with an ultimate result thatachieving a sound and complete simulator, which operates only in a single operating regionin which continuity rules are fully obeyed, is impossible,. The results in this thesis are demonstrated using the QSIM representation for inputand output, and are valid for all qualitative simulators whose input and output vocabulariesare identical to that of QSIM. They are important in the sense that they provide deeperinsight to the causes of spurious predictions, and they are also interesting for researchersaiming to construct provably sound and complete simulators using weaker representations.