What do we believe?

Mathematics is mainly the process of certifying truth by proofs. However, Gödel's incompleteness theorems show that there are always true sentences which are not provable. So a natural question is, regarding this incompleteness phenomenon, is it possible to find a new way of certifying truth, in a way by which we can still "believe" some unprovable truth?

We will examine one such approach. We define a sentence to be "believable", roughly speaking, that the base theory can prove that the sentence is provable from a true sentence. We also need to formalize this notion correctly to avoid Tarski's undefinabiliy of truth. We give an exact characterization of the believable sentences using the notion of Sigma_n-soundness. Slides

A Restricted Four-valued Logic for Default Reasoning

Reiter's default logic is a widely studied nonmonotonic logic. In Reiter's default logic, it is possible that no useful information can be brought from inconsistent knowledge or no extension of incoherent default theories exists. In this report, based on Belnap's four-valued logic, we introduce a new variant of default logic called the restricted four-valued default logic to tolerate inconsistency and incoherency of knowledge in default reasoning. Our proposal can maintain both the expressive power of full default logic and the ability of default reasoning. Slides

Naturalism and Mathematical Realism

Since the naturalistic turn in general philosophy around the 1950s, it has become more and more natural to consider ontological questions in the philosophy of mathematics from naturalistic perspectives. Particularly, there can be found two leading paths from naturalism to mathematical realism in the literature: the classic indispensability argument provided by W. V. Quine and Hilary Putnam, and the radical naturalistic one advocated by John Burgess and Gideon Rosen. The first is one of the most influential arguments in contemporary philosophy of mathematics, and appeals to the applications of mathematics in natural sciences to champion mathematical realism. The second is relatively not so widely discussed, but tries to do more justice to mathematical sciences and defend mathematical realism more directly. In this talk, I will examine both of these two paths, comparing their difference and present my reactions to them. I will distinguish two versions of the indispensability argument and point out their weakness respectively. I will object the Burgess-Rosen naturalistic argument for realism and show that their version of naturalism cannot avoid the Benaccerraf problem as they claim. Slides

A logic framework for conformant planning: a journey from philosophy to AI (and back)

Based on the philosophical idea that “meaning as potential change” we propose an epistemic dynamic logic to describe the changes of uncertainty in the context of conformant planning, i.e., the problem of finding a linear plan under initial uncertainty. The traditional conformant planning problem can be then viewed as a particular kind of model checking problem in our framework. We show that the model checking problem of our logic is PSPACE-complete. Based on our result, the standard conformant planning problem in AI can be largely generalized without paying the price in computational complexity, which demonstrates the advantage of this logic-based approach. In the end we use the idea in our planning framework to give an intuitive semantics for a logic of “knowing how”, which may bring new insights to the philosophical discussion between knowledge-how and knowledge-that.

The talk is mostly based on the following papers:

Computing halting probabilities from other halting probabilities

Chaitin’s Omega number depends on the underlying universal enumeration of prefix-free ma- chines but its Turing degree is always the same as that of the halting problem. In particular, given two universal prefix-free machines $U,V$, the halting probability of $U$ computes the halting probability of $V$. It can be observed that the number of bits of the second halting probability that are needed for the computation of the first $n$ bits of the first halting probability is bounded by a computable use-function $g(n) = n + o (n)$.

We characterize the use-functions $g$ such that given every pair of omega numbers, each is computable from the other with use $g$. We do the same with respect to pairs of an omega number and a computably enumerable set. As an application, we get a characterization of the Solovay functions (recently studied by a number of authors) in terms of use-functions for computations between omega numbers.