ABSTRACTCOMPUTABILITY-THEORETIC LIMITATIONS OF QUALITATIVESIMULATIONQualitative 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 usuallyaugmented 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 andoutput 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 therebyestablishes 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 forseveral ?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.

ÖZETN TEL BENZET M N HESAPLANAB L RL K KURAMINA DAYALISINIRLARINitel uslamlama ve benzetim, özellikle dinamik sistemlerin analizi, tasarımı ve tanısıiçin faydalı matematiksel araçlardır. Eksik, yani belirli bir girdi için yanlış tahmin üretenbenzeticilere, genellikle o davranışı elimine eden ilave süzgeçler eklenir. Kuipers tutarlılıközelliğini içeren, bir başka deyişle, çıktısında, girdiye uyan nicel bir denklemin sonucu olanhiçbir davranışı kaçırmayan bir benzetici (QSIM) sunmuştur. Girdi ve çıktı alfabesi ?saf?QSIM ile aynı olan tutarlı ve tam bir benzeticinin varolmadığı ispatlanmıştır.Bu tez, nitel benzetimin hesaplanabilirlik kuramına dayalı sınırları üzerine bir seri ilavesonuçlar içermektedir. lk olarak, herhangi bir sınırsız yazmaçlı makinenin modellemesi vebenzetimi için bir method ortaya koymakta ve bununla nitel benzetimin evrensel hesaplamagücüne sahip olduğunu tesis etmektedir. Evrensel hesaplama gücüne sahip olan hesaplamaaraçlarının meşhur kararlaştırılamaz Durma Problemi'nden indirgeme yardımıyla, girdi veçıktı da QSIM alfabesi kullanmak suretiyle, girdi ve çıktı alfabesinin pek çok ?daraltılmış?versiyonu için, tutarlı ve tam bir benzetici yapılamayacağını ispat etmektedir. Çalışma, içindesüreklilik kurallarına tamamı ile uyulduğu tek bir çalışma alanı içinde işleyen tutarlı ve tambir benzetici elde etmenin imkansız olduğunu kanıtlayan nihai bir ispatla sona ermektedir.Bu tezdeki sonuçlar QSIM girdi ve çıktı alfabesi kullanılarak ortaya konmuştur ve girdiçıktı alfabesi QSIM ile aynı olan tüm benzeticiler için geçerlidir. Sonuçlar, yanlış tahminlerinsebepleri ile ilgili daha derin ipuçları vermeleri açısından önemlidir ve daha daraltılmıştemsili alfabeler kullanarak tutarlı ve tam nitel benzeticiler yaratmaya çalışan araştırmacılarıyakınen ilgilendirmektedir.