# Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science (Computer Science and Applied Mathematics)

## Martin Davis

Language: English

Pages: 425

ISBN: 0122063805

Format: PDF / Kindle (mobi) / ePub

This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.

* Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page.

* The number of exercises included has more than tripled.

* Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.

language, the possibility of interpretive programs, the duality between software and hardware, and the representation of languages by formal structures, based on productions. While the spotlight in computer science has tended to fall on the truly breathtaking technolog ical advances that have been taking place, important work in the founda tions of the subject has continued as well. It is our purpose in writing this book to provide an introduction to the various aspects of theoretical computer

i.e., /(z) = f(x{,..., x„). If, on the other hand, the right side is undefined, it must be the case that STP (W) (A"| , . . . , xn,y{),t) is false for all values of /, i.e., f(xx,..., xn)î . ■ The normal form theorem leads to another characterization of the class of partially computable functions. Theorem 3.4. A function is partially computable if and only if it can be obtained from the initial functions by a finite number of applications of composition, recursion, and minimalization. Proof.

{1,2,3}. Work out the multiplication 40 • 12 = 480 in base 3. Compute CONCAT„(12,15) for n = 3, 5, and 10. Why is no calculation required in the last case? Compute the following: U P C H A N G E , 7 (15), UPCHANGE, 7(15), UPCHANGE 2 10(15), DOWNCHANGE 3 7(15), DOWNCHANGE 2 7(15), DOWNCHANGE 2 ,,„(20). 2. Compute each of the following for n = 3. (a) CONCAT<2)(17,32). (b) CONCAT, ( ; 3) (17,32,ll). (c) RTEND,;(23). (d) LTEND„(29). (e) RTRUNC„(19). (f) LTRUNC„(18). 3. Do the previous exercise

Chapter 5. 5. Construct Turing machines for Exercise 4.4 in Chapter 5. 6. Construct a Turing machine for Exercise 4.5 in Chapter 5. 7. Using the construction in the proof of Theorem 1.1, transform the Post-Turing program in Figure 4.4 of Chapter 5 into an equivalent Turing machine. 8. Using the construction in the proof of Theorem 1.3, transform the Turing machine in Table 1.1 into an equivalent quintuple Turing machine. 9. Construct a quintuple Turing machine that computes fix, y) = x —

having programming experience will find working with òf very easy. In äf we will be able to write "instructions" of various sorts; a "program" of Sf will then consist of a list (i.e., a finite sequence) of 17 18 Chapter 2 Programs and Computable Functions Table 1.1 Instruction Interpretation V <- V + 1 V <— V - 1 Increase by 1 the value of the variable V. If the value of V is 0, leave it unchanged; otherwise decrease by 1 the value of V. IF V =£ 0 GOTO L If the value of V is nonzero,