# Computability Theory: An Introduction to Recursion Theory

## Herbert B. Enderton

Language: English

Pages: 192

ISBN: 0123849586

Format: PDF / Kindle (mobi) / ePub

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

Elementary Algebra (9th Edition)

Real Analysis: Measures, Integrals and Applications (Universitext)

Solving Mathematical Problems: A Personal Perspective

Introduction to Modern Cryptography: Principles and Protocols

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 h(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

the size of the jump. Next, to a program c0 , . . . , cm (i.e., a finite string of instructions), we assign its Go¨ del number [#c0 , . . . , #cm ]. To the empty program, we assign the Go¨ del number 1. For example, the one-line program I 0 has the Go¨ del number [6] = 27 = 128. And the one-line program J −1 has the Go¨ del number [ [3, 1] ] = 2145 . For example, what is (128, 7)? First, we decode 128 = [6] = [#I 0]. Next, we apply this program to 7, obtaining an output of 1. We conclude that

∃y[θ(x2 , y) and δ(x2x1 , y) and not δ(x2Sx1 , y)] defines the graph of the function t → pt in arithmetic. Lemma: The graph of the decoding function s, t → (s)t is definable in arithmetic. Proof. The key fact is that if s = 0 0 if pt s (s)t = 0 e+2 the e for which pe+1 | s and p s otherwise. t t Connections to Logic 115 Using the expression δ(x1 , x2 ) for divisibility and the expression ψ(x1 , x2 ) for the graph of t → pt , we can make the expression (x1 = 0 and x3 = 0) or ∃y(ψ(x2 , y)

(x) > g(x) for all but finitely many values of x). 7 Polynomial-Time Computability 7.1 Feasible Computability Up to now, we have approached computability from the point of view that there should be no constraints either on the time required for a particular computation or on the amount of memory space that might be required. The result is that some total computable functions will take a very long time to compute. If a function f grows very rapidly, then for large x, it will take a long time

the squaring function. Proposition: Any polynomial function p(x) is P-time computable. Proof outline. We build up the polynomial piece by piece, using the foregoing examples. Raising x to a power (that is, the function x → xk ) can be done by composition of multiplications. A monomial x → cxk involves one more multiplication, this time by a constant. Finally, we use a composition of additions. Example: Let 2 f (x) = 2|x| = 100 · · · 0two , where the string of 0’s is |x|2 long. This function can