Computing with causal theories

Abstract

ÖZET NEDENSEL TEORİLERLE HESAPLAMA Erkan Tın Yüksek Lisans Tezi, Bilgisayar ve Enformatik Mühendisliği Bölümü Tez Yöneticisi: Doç. Dr. Varol Akman Ekim 1990 Zaman üzerine çıkarım yapılabilmesi için sağduyu bilgisinin formel hale sokulması uzun zamandır Yapay Zekâ'nm (YZ) merkezi meselesi olmuştur. Halihazırdaki formel sistemlerin YZ'nin çerçeve sorunu gibi bazı temel problemlerine tatmin edici çözümler getirmedikleri bilinmektedir. Dahası, bu sistemlerle yapılan çıkarımlar aksiyomlarla ifade edilmek istenenlerle daima uyuşmamaktadır. Bu meseleler zaman ve değişim üzerine çıkarım yapılabilmesi için iyi tanımlanmış bir formelizmi ve yararlı hesaplama metodlarını davet etmektedir. Stanford Üniversitesi'nden Yoav Shoham doktora tezinde (Yale, 1986) kronolojik bilgisizlik adım verdiği temporel, tekdüze olmayan cazip bir mantık ortaya koymuş ve nedensel teoriler olarak adlandırılan, hesaplaması basit model teorik özellikleri bulunan bir teori sınıfı tanımlamıştır. Bu sınıfın bazı sınırlamaları olduğu için bu tez Shoham'm nedensel teorileri üzerine yapılan bir geliştirme çalışmasıdır. Tez özellikle bu teorilerin hesapsal yönlerinin onların model teorik özelliklerim koruyarak iyileştirilmesi etrafında yoğunlaşmaktadır. Anahtar Kelimeler: Nedensellik, nedensel teoriler, çerçeve sorunu, kalifiye olma sorunu, kalıcılık sorunu, modal mantıklar, tekdüze olmayan mantıklar, temporel mantıklar, kronolojik bilgisizlik, model teorisi. iv

ABSTRACT COMPUTING WITH CAUSAL THEORIES Erkan Tin M. S. in Computer Engineering and Information Sciences Supervisor: Assoc. Prof. Varol Akman October 1990 Formalizing commonsense knowledge for reasoning about time has long been a central issue in Artificial Intelligence (AI). It has been recognized that the existing formalisms do not provide satisfactory solutions to some fundamental problems of AI, viz. the frame problem. Moreover, it has turned out that the inferences drawn by these systems do not always coincide with those one had intended when he wrote the axioms. These issues call for a well-defined formalism and useful computational utilities for reasoning about time and change. Yoav Shoham of Stanford University introduced in his 1986 Yale doctoral thesis ah appealing temporal nonmonotonic logic, the logic of chronological ignorance, and identified a class of theories, causal theories, which have computationally simple model-theoretic properties. This thesis is a study towards building upon Shoham' s work on causal theories for the latter are somewhat limited. The thesis mainly centers around improving computational aspects of causal theories while preserving their model-theoretic properties. Keywords: Causation, causal theories, the frame problem, the qualification problem, the persistence problem, modal logics, nonmonotonic logics, temporal logics, chronological ignorance, model theory. Ill