Computability Theory (eBook)

An Introduction to Recursion Theory

Herbert B. Enderton (Autor)

eBook Download: PDF | EPUB

2010 | 1. Auflage
192 Seiten
Elsevier Science (Verlag)
978-0-12-384959-5 (ISBN)

Infos

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

Inhalt

Front Cover 1
Computability Theory 4
Copyright 5
Dedication 6
Table of Contents 8
Foreword 10
Preface 
12 
Chapter 1. The Computability Concept 14
1.1 The Informal Concept 14
Exercises 24
1.2 Formalizations – An Overview 25
Exercises 40
Chapter 2. General Recursive Functions 42
2.1 Primitive Recursive Functions 42
2.2 Search Operation 60
Exercises 62
Chapter 3. Programs and Machines 66
3.1 Register Machines 66
3.2 A Universal Program 73
Exercises 84
3.3 Register Machines Over Words 85
Exercises 89
3.4 Binary Arithmetic 89
Chapter 4. Recursive Enumerability 92
4.1 Recursively Enumerable Relations 94
Exercises 105
4.2 Parameters 106
Exercises 113
Chapter 5. Connections to Logic 116
5.1 Arithmetical Hierarchy 116
Exercises 124
5.2 Definability in Arithmetic 124
5.3 The Complexity of Truth 129
Exercises 133
Chapter 6. Degrees of Unsolvability 134
6.1 Relative Computability 134
6.2 Equivalence Relations 140
6.3 Preordering Relations 143
6.4 Ordering Degrees 144
Exercises 145
6.5 Structure of the Degrees 145
Exercises 150
Chapter 7. Polynomial-Time Computability 152
7.1 Feasible Computability 152
7.2 P versus NP 160
7.3 Some Other Complexity Classes 161
Exercises 162
Appendix 1. Mathspeak 164
Appendix 2. Countability 168
Appendix 3. Decadic Notation 172
References 176
Index 178

Textauszug

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 one 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 m = 1 and the function (w,y)=w⋅(y+1). Then the function h obtained by primitive recursion from g by using m 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 h:

(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 h(4), we first need to know h(3), and to find that we need h(2), and so on. The function h in this example is, of course, better known as the factorial function, h(x) = x!.

It should be pretty clear that given any number m and any two-place function g, there exists a unique function h obtained by primitive recursion from g by using m. It is the function h that we calculate as in the preceding example. Similarly, given a k-place function f and a k+2)-place function g, there exists a unique k+1)-place function h that is obtained by primitive recursion from f and g. That is, h 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 f and g are total functions, then h will also be total.

Example

Consider the addition function (x,y)=x+y. For any fixed x, its value at y + 1 (i.e., x + y + 1) is obtainable from its value at y (i.e., x + y) 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 f and g are primitive recursive; f is the projection function 11, and g 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 h, we can use a labeled tree (“construction tree”) to illustrate exactly how h is built up, as in the example of addition. At the top (root) vertex, we put h. 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 f must be an n-place function, and 1,…,gn must all have the same number of places as h.

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

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 g must have two more places than f, and one more place than h (e.g., if h is a two-place function, then g must be a three-place function and f must be a one-place function).

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

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 t. The role of g 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 x or t) in place of this pronoun. This leads us to the names “the function whose value at x is x2” or “the function whose value at t is t2.” More compactly, these names can be written in symbols as “↦x2” or “↦t2.” The letter x or t is a dummy variable; we can use any letter here.

2. Any constant function →↦k can be obtained by applying composition k 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...

Produkt-Details

• Erscheint lt. Verlag: 30.12.2010
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Informatik ► Office Programme ► Outlook
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-12-384959-4 / 0123849594
• ISBN-13: 978-0-12-384959-5 / 9780123849595