Definition 2.1.1

(Blum space) A Blum space ϕ is a sequence of pairs of functions ((φi , Φi ))i ε, such that

(a)  (φi )i ∈is an acceptable gödelization of the set of partial computable functions, and

(b)  The system (φi , Φi )i ∈ satisfies the two Blum axioms .

To understand the justification of the two axioms, we recommend the reader to mentally check that the natural computational resources listed above satisfy the two Blum axioms.1 Consequently, the theory of abstract complexity measures (more concisely known as abstract complexity theory or Blum complexity theory) applies to them and, in fact, to virtually every natural resource in any conceivable realistic model of computation. It is remarkable that the two simple Blum axioms lead to deep results of extreme generality.

In this chapter, we will present the most important results of abstract complexity theory, including answers to the questions (1), (2), and (3). In the spirit of this book, we will not content ourselves with just showing the existence of functions having interesting properties (such as, for example, functions for which the answer to question (2) is negative). We will also analyze such results quantitatively by looking at the size of classes of such functions from a topological or measure-theoretical point of view.

The topological analysis follows the ideas presented in Section 1.2.1 . We use the Cantor topology . In our context, it is convenient to view the finite strings over the alphabet (or {0,1}) that define the base of the Cantor topology in the space of p.c. functions (or, respectively, p.c. predicates) as being functions whose domain is an initial segment of . In the rest of our discussion we consider the case of p.c. functions, and just note that the p.c. predicates can be treated similarly.

For f , g ∈ PC, we write f g in case

(f)⊂─dom(g)?and?f(x)=g(x),?for?every?x?in?dom(f).

For every t ∈ FPC, let

t={f∈PC|t⊑f}.

The family (U t )t ∈FPCis a system of basic neighborhoods in PC defining the Cantor topology in the set of p.c. functions; we work with the topology generated by this system. In the classical framework (see the discussion in Section 1.2.1 ; for notation, see Section 1.1.1 ), a set A in a topological space is nowhere dense (or rare ) if for every non-empty open set O there exists a non-empty open subset O ′ ⊆ O such that O ′ ∩ A = ∅. A set is of first Baire category (or meagre ) if it is a finite or denumerable union of nowhere dense sets, and it is of the second Baire category if it is not meagre . In the effective variant of these notions, the open set O ′ is obtained effectively from O . Formally, there exists a computable function f that for almost every basic open set U t produces a witness f (t ) which indicates a basic open set U f (t )that is disjoint with the nowhere dense set. These ideas lead to the following definition.

1 Sometimes, we may need to do inconsequential modifications in the standard definition of a complexity measure. For instance, to conform to axiom (BA 1), we can assume that the space used in a non-halting computation is infinite.

Definition 2.1.2

(Effective Baire classification)

(1)  A set X of p.c. functions is effectively nowhere dense if there exists a computable function f, called the witness function, such that:

(i)  αn αf (n ), for all n ∈ ,

(ii)  There exists j ∈ such that, for all n ∈ , |αn | > j implies

∩Uαf(n)=∅.

(2)  A set X of p.c. functions is effectively of first Baire category (or effectively meagre) if there exist a sequence of sets (X i )i ∈and a computable function f such that

(i)  X = ∪i ∈X i and, for all i ∈ ,

(ii)  αn αf (〈i,n 〉), for all n ∈ N,

(iii)  there exists j ∈ such that, for all n ∈ , |αn | > j implies

i∩Uαf(<i,n>)=∅.

(3)  A set X of p.c. functions is a set effectively of second Baire category if X is not a set of effectively first Baire category .

In the rest of this chapter, we only consider the above effective version of Baire classification. For conciseness, we usually drop the word effectively in the above terminology.

The subsets of the set of p.c. functions can be classified with respect to the following hierarchy of sets of increasing size: nowhere dense, first Baire category (or meagre), second Baire category, co-meagre, and co-nowhere dense sets (see Definition 1.2.1 ). Intuitively, from a topological point of view, a nowhere dense set is tiny, a first Baire category set is small, a second Baire category set is not small, and co-meagre and co-nowhere dense sets are large.

One can easily observe that the extensions in the above definition can be taken to be proper (), and this will be the case in all our further considerations.

As mentioned, a topology over the set of p.c. predicates can be introduced similarly. The above definition can be stated in terms of the relativized topology of p.c. predicates (i.e., {0,1}-valued functions), by simply considering that (αn )n ∈enumerates FPRED, the set of all p.c. predicates having the domain equal to a finite initial segment of , (i.e., each αn can be considered to be a binary string). In this case, the topology is generated by the basic open sets (U t )t ∈FPRED, where

t={f|t⊑f,f?is?a?p.c.?predicate}.

This abuse of notation (i.e., we use the same notation for the basic open sets of both PC and PRED) will always be clarified by context.

IN BRIEF: Any complexity class is topologically small.