Thinking on the Web: Berners-Lee, Gödel and Turing

2

GÖDEL: WHAT IS DECIDABLE?

OVERVIEW

In Chapter 1, we suggested that small wireless devices connected to an intelligent Web could produce ubiquitous computing and empower the Information Revolution. In the future, Semantic Web architecture is designed to add some intelligence to the Web through machine processing capabilities. For the Semantic Web to succeed, the expressive power of the logic added to its markup languages must be balanced against the resulting computational complexity.¹ Therefore, it is important to evaluate the expressive characteristics of logic languages, as well as their inherent limitations.

In fact, some options for Web logic include solutions that may not be solvable through rational argument. In particular, the work of Kurt Gödel identified the concept of undecidability where the truth or falsity of some statements may not be determined.

In this chapter, we review some of the basic principles of logic and relate them to the suitability for Web applications. First, we review the basic concept of logic and discuss various characteristics and limitations of logic analysis. We introduce First-Order Logics (FOL) and its subsets, such as Descriptive Logic and Horn Logic, which offer attractive characteristics for Web applications. These languages set the parameters for how expressive Web markup languages can become.

Second, we investigate how logic conflicts and limitations in computer programming and Artificial Intelligence (AI) have been handled in closed environments ...