|
|
|
|
|
|
We now review the standard notations and definitions to be used in the sequel. This material is designed to be more of a reference than part of our main story. So we advise the reader to skim the present chapter, consulting it later as needed. |
|
|
|
|
|
|
|
|
What We Assume of the Reader. |
|
|
|
|
|
|
|
|
We assume that the reader has some background in the theory of computation. In particular, we assume the reader is acquainted with the Church-Turing Thesis, the existence of universal Turing machines, the unsolvability of the halting problem, the partial recursive functions, the (total) recursive functions, and the recursively enumerable sets. Almost any text on the theory of computation covers these topics. See, for example, any of Rogers [158], Hopcroft and Ullman [82], Cutland [45], and Lewis and Papadimitriou [126]. |
|
|
|
|
|
|
|
|
N denotes the set of natural numbers { 0, 1, 2, . . . } and N+ denotes the set of positive integers; '#' and '*' are special constants that are not elements of N. For two natural numbers m and n, |
|
|
|
|
|
|
|
|
If a symbol is said to be a variable that ranges over a particular domain, then by convention decorated versions of the symbol (e.g., superscripted and subscripted versions of the symbol) are also variables over the same domain. Generally, e, i, j, k, l, m, n,, . . ., x, y, z range over N; a, b, c, d range over  ; f, g, h, p, q, and r range over total functions from N to N; and h , n , q , and x range over (possibly) partial functions from N to N. Uppercase roman letters are generally used as variables over subsets of N and sometimes Nk for some k> 1. Upper case script letters, A, B, C, . . ., are generally used as variables ranging over classes of sets or functions. |
|
|
|
|
|
|
|
|
The symbols  ,  ,  , and  denote proper subset, proper superset, subset (possibly proper) and superset (possibly proper), respectively.  denotes 'element of.'  denotes the empty set. card(A) denotes the cardinality of A.  denotes card(N) and  denotes the cardinality of the power-set of N. min(A) denotes the minimum element of A, where  . max(A) denotes the maximum element of A, where  |
|
|
|
|
