Algorithmic knowledge

In the previous chapter I have developed a framework for reasoning about explicit knowledge. The strategy is to take the cost of inferring new information into account. Following this strategy a number of logics have been defined which can solve all variants of the logical omniscience problem and at the same time can account for the intuition that agents are rational beings. In my framework it is possible to model situations where an agent's explicit knowledge is not closed under any logical law: he may know all premises of an inference rule without knowing the conclusion. But this does not mean he is logically ignorant. On the contrary, he may well be perfectly rational: if he chooses to draw a conclusion of his knowledge and if he has sufficient computational resources, he will eventually succeed in doing it. Thus, resource-bounded reasoning can be modeled realistically: an agent's lack of logical omniscience stems from his resource-boundedness, and not from his inability to use certain logical rules.

However, there are a number of situations where resource-bounded
reasoning cannot be modeled within the framework of explicit knowledge
considered so far. First of all, the dynamic-epistemic systems of the
previous chapter are based on standard qualitative temporal logic and
are therefore not suited to describe quantitative time
constraints^{5.1}. Moreover, they have too little expressive
power for modeling meta-reasoning, i.e., for modeling how an agent
reasons about the reasoning process of himself or of other agents.

In this chapter I shall introduce a new concept of knowledge which allows quantitative resource constraints to be formalized directly. This concept generalizes both concepts of explicit and implicit knowledge and avoids the problems of the existing approaches. In the next section I shall discuss the concept informally. Then I proceed to define a formal language and some formal systems for resource-bounded reasoning about knowledge. Finally, comparisons with other notions of knowledge will be made.