Enderton Computability Theory

An Introduction to Recursion Theory
1. Auflage 2010
ISBN: 978-0-12-384959-5
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 192 Seiten

Computability Theory: An Introduction to Recursion Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The text includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable way. - Frequent historical information presented throughout - More extensive motivation for each of the topics than other texts currently available - Connects with topics not included in other textbooks, such as complexity theory

Autoren/Hrsg.

Enderton, Herbert B.

Inhaltsverzeichnis

1;Front Cover;1
2;Computability Theory;4
3;Copyright;5
4;Dedication;6
5;Table of Contents;8
6;Foreword;10
7;Preface
;12
8;Chapter 1. The Computability Concept;14
8.1;1.1 The Informal Concept;14
8.2;Exercises;24
8.3;1.2 Formalizations – An Overview;25
8.4;Exercises;40
9;Chapter 2. General Recursive Functions;42
9.1;2.1 Primitive Recursive Functions;42
9.2;2.2 Search Operation;60
9.3;Exercises;62
10;Chapter 3. Programs and Machines;66
10.1;3.1 Register Machines;66
10.2;3.2 A Universal Program;73
10.3;Exercises;84
10.4;3.3 Register Machines Over Words;85
10.5;Exercises;89
10.6;3.4 Binary Arithmetic;89
11;Chapter 4. Recursive Enumerability;92
11.1;4.1 Recursively Enumerable Relations;94
11.2;Exercises;105
11.3;4.2 Parameters;106
11.4;Exercises;113
12;Chapter 5. Connections to Logic;116
12.1;5.1 Arithmetical Hierarchy;116
12.2;Exercises;124
12.3;5.2 Definability in Arithmetic;124
12.4;5.3 The Complexity of Truth;129
12.5;Exercises;133
13;Chapter 6. Degrees of Unsolvability;134
13.1;6.1 Relative Computability;134
13.2;6.2 Equivalence Relations;140
13.3;6.3 Preordering Relations;143
13.4;6.4 Ordering Degrees;144
13.5;Exercises;145
13.6;6.5 Structure of the Degrees;145
13.7;Exercises;150
14;Chapter 7. Polynomial-Time Computability;152
14.1;7.1 Feasible Computability;152
14.2;7.2 P versus NP;160
14.3;7.3 Some Other Complexity Classes;161
14.4;Exercises;162
15;Appendix 1. Mathspeak;164
16;Appendix 2. Countability;168
17;Appendix 3. Decadic Notation;172
18;References;176
19;Index;178

Leseproben

2

General Recursive Functions

Publisher Summary

This chapter focuses on primitive recursiveness and search, which give the class of general recursive partial functions. It develops tools for showing that certain functions are in this class. These tools are used to study computability by register-machine programs. The search operator provides a useful way of defining a function in terms of a “search” for the first time a given condition is satisfied. Earlier the collection of primitive recursive functions cannot contain all of the effectively calculable total functions. This chapter presents theorem to show that the constructions preserve primitive recursiveness. That is, when applied to primitive recursive relations, they produce primitive recursive relations. This theorem is useful in extending the supply of primitive recursive relations and functions. The class of general recursive partial functions is obtained that allows functions to be built up by use of search.

In the preceding chapter, we saw an overview of several possible formalizations of the concept of effective calculability. In this chapter, we focus on of those: primitive recursiveness and search, which give us the class of general recursive partial functions. In particular, we develop tools for showing that certain functions are in this class. These tools will be used in Chapter 3, where we study computability by registermachine programs.

2.1 Primitive Recursive Functions

The primitive recursive functions have been defined in the preceding chapter as the functions on that can be built up from zero functions

(x1,…,xk)=0,

the successor function

(x)=x+1,

and the projection functions

nk(x1,…,xk)=xn

by using (zero or more times) composition

(x?)=f(g1(x?),…,gn(x?))

and primitive recursion

(x?,0)=f(x?)h(x?,y+1)=g(h(x?,y),x?,y),

where ? can be empty:

(0)=mh(y+1)=g(h(y),y).

Example

Suppose we are given the number = 1 and the function (w,y)=w·(y+1). Then the function obtained by primitive recursion from by using is the function given by the pair of equations

(0)=m=1h(y+1)=g(h(y),y)=h(y)·(y+1).

Using this pair of equations, we can proceed to calculate the values of the function :

(0)=m=1h(1)=g(h(0),0)=g(1,0)=1h(2)=g(h(1),1)=g(1,1)=2h(3)=g(h(2),2)=g(2,2)=6h(4)=g(h(3),3)=g(6,3)=24

And so forth. In order to calculate (4), we first need to know (3), and to find that we need (2), and so on. The function in this example is, of course, better known as the factorial function, () = !.

It should be pretty clear that given any number and any two-place function , a unique function obtained by primitive recursion from by using . It is the function that we calculate as in the preceding example. Similarly, given a -place function and a k+2)-place function , there exists a unique k+1)-place function that is obtained by primitive recursion from and . That is, is the function given by the pair of equations

(x?,0)=f(x?)h(x?,y+1)=g(h(x?,y),x?,y).

Moreover, if and are total functions, then will also be total.

Example

Consider the addition function (x,y)=x+y. For any fixed , its value at + 1 (i.e., + + 1) is obtainable from its value at (i.e., + ) by the simple step of adding one:

+0=xx+(y+1)=(x+y)+1.

This pair of equations shows that addition is obtained by primitive recursion from the functions (x)=x and (w,x,y)=w+1. These functions and are primitive recursive; is the projection function 11, and is obtained by composition from successor and 13. Putting these observations together, we can form a tree showing how addition is built up from the initial functions by composition and primitive recursion:

More generally, for any primitive recursive function , we can use a labeled tree (“construction tree”) to illustrate exactly how is built up, as in the example of addition. At the top (root) vertex, we put . At each minimal vertex (a leaf), we have an initial function: the successor function, a zero function, or a projection function. At each other vertex, we display either an application of composition or an application of primitive recursion.

An application of composition

(x?)=f(g1(x?),…,gn(x?))

can be illustrated in the tree by a vertex with n+1)-ary branching:

Here must be an -place function, and 1,…,gn must all have the same number of places as .

An application of primitive recursion to obtain a k+1)-place function

h(x?,0)=f(x?)h(x?,y+1)=g(h(x?,y),x?,y)

can be illustrated by a vertex with binary branching:

Note that must have two more places than , and one more place than (e.g., if is a two-place function, then must be a three-place function and must be a one-place function).

The =0 case, where a one-place function is obtained by primitive recursion from a two-place function by using the number

h(0)=mh(x+1)=g(h(x),x),

can be illustrated by a vertex with unary branching:

In both forms of primitive recursion (>0 and =0), the key feature is that the value of the function at a number +1 is somehow obtainable from its value at . The role of is to explain how.

Every primitive recursive function is total. We can see this by “structural induction.” For the basis, all of the initial functions (the zero functions, the successor function, and the projections functions) are total. For the two inductive steps, we observe that composition of total functions yields a total function, and primitive recursion applied to total functions yields a total function. So for any primitive recursive function, we can work our way up its construction tree. At the leaves of the tree, we have total functions. And each time we move to a higher vertex, we still have a total function. Eventually, we come to the root at the top, and conclude that the function being constructed is total.

Next we want to build up a catalog of basic primitive recursive functions. These items in the catalog can then be used as “off the shelf” parts for later building up of other primitive recursive functions.

1. Addition x,y>?x+y has already been shown to be primitive recursive.
The symbol “” is read “maps to.” The symbol gives us a very convenient way to name functions. For example, the squaring function can be named by the lengthy phrase “the function that given a number, squares it,” which uses the pronoun “it” for the number. It is mathematically convenient to use a letter (such as or ) in place of this pronoun. This leads us to the names “the function whose value at is 2” or “the function whose value at is 2.” More compactly, these names can be written in symbols as “?x2” or “?t2.” The letter or is a dummy variable; we can use any letter here.

2. Any constant function ??k can be obtained by applying composition times to the successor function and the zero function ??0. For example, the three-place function that constantly takes the value 2 can be constructed by the following tree:

3. For multiplication x,y>?x×y, we first observe that

×0=0x×(y+1)=(x×y)+x.

This shows that multiplication is obtained by primitive recursion from the functions ?0 and w,x,y>?w+x. The latter function is obtained by composition applied to addition and projection functions.
We can now conclude that any polynomial function with positive coefficients is primitive recursive. For example, we can see that the function (x,y)=x2y+5xy+3y3 is primitive recursive by repeatedly applying 1, 2, and...