Информатика и вычислительная техника
  • формат djvu
  • размер 4.9 МБ
  • добавлен 12 октября 2011 г.
Rogers H. Theory of Recursive Functions and Effective Computability
Издательство McGrow-Hill, 1967, -504 pp.

In addressing the American Mathematical Society in 1944, E. L. Post concluded, "Indeed, if general recursive function is the formal equivalent of effective calculability, its formulation may play a role in the history of combinatory mathematics second only to that of the formulation of the concept of natural number."
This book may be viewed as a progress report on some of the ideas and hopes expressed in Post's paper. The subject of recursive functions had been studied by a number of researchers prior to 1944. In particular, Church, Kleene, and Turing, as well as Post himself, had already made major contributions. Although Post's paper conces only one part of a larger subject, it marks an epoch in that subject, not only for the specific problems and methods that it presents, but also for the emphasis that it places on intuitive naturalness in basic concepts.
Post's remark, quoted above, is undoubtedly extravagant; and one may well question whether the kind of calculability represented by general recursive functions will possess a theory of much practical usefulness. (We dis- cuss this further in Chapter
1.) Nevertheless, this book is intended to be a partial vindication of Post's remark and of his attitude. The book presents its subject matter in semiformal terms, with an intuitive emphasis that is, hopefully, appropriate and instructive. The use of semiformal procedures in recursive function theory is analogous to the use, in other parts of mathematics, of set-theoretical arguments that have not been fully formalized. It is possible for one who possesses a good grasp of the simple, primitive ideas of our theory to do research, just as it is possible for a student of elementary algebra in school to do research in the theory of natural numbers. Since 1944, and especially since 1950, the subject of recursive function theory has grown rapidly. Many researchers have been active. The present book is not intended to be comprehensive or definitive. Moreover, its informal and intuitive emphasis will prove, in some respects, to be a limitation. Certain important parts of the theory (e.g., the study of various proper subclasses of the general recursive functions) and certain interesting applications (e.g., the identification of recursively unsolvable problems in other parts of mathematics) cannot, by their nature, be treated without more extensive and detailed formalism. Several works already exist to supply this defect, and the reader is urged to use them as a more formal supplement to the present text. One of these is Kleene's Introduction to metamathematics, D. Van Nostrand Company, Inc., Princeton, N.J., 1952; another is Davis's Computability and unsolvability, McGraw-Hill Book Company, New York, 1958. These works, while valuable as a supplement, are not a prerequisite for this book.
The book is in sixteen chapters. Chapters 1 and 2 present the basic concept of partial recursive function and give simple examples of the unsolvability phenomenon. Chapters 3 and 4 summarize and characterize the theory to be developed. Chapter 5 gives further basic concepts. Chapters 6 to 10 present results on reducibilities and degrees of unsolvability (concepts emphasized in Post's 1944 paper). Chapter 11 presents the recursion theorem, a fundamental tool in the theory. Chapters 12 to 16 present certain major areas of current research activity. A more detailed outline of the book is given in Chapter 3.

Recursive Functions
Unsolvable Problems
Purposes; Summary
Recursive Invariance
Recursive and Recursively Enumerable Sets
Reducibilities
One-One Reducibility; Many-One Reducibility; Creative Sets
Truth-Table Reducibilities; Simple Sets
Turing Reducibility; Hypersimple Sets
Post's Problem; Incomplete Sets
The Recursion Theorem
Recursively Enumerable Sets as a Lattice
Degrees of Unsolvability
The Arithmetical Hierarchy (Part 1)
The Arithmetical Hierarchy (Part 2)
The Analytical Hierarchy
Возможность скачивания данного файла заблокирована по требованию правообладателя.
Похожие разделы
Смотрите также

Atallah M.J., Blanton M. (eds.) Algorithms and Theory of Computation Handbook. General Concepts and Techniques

Справочник
  • формат pdf
  • размер 8.46 МБ
  • добавлен 30 января 2012 г.
Издательство Chapman&Hall/CRC Press, 2010, -990 pp. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of al...

Bednorz W. (ed.) Advances in Greedy Algorithms

  • формат pdf
  • размер 55.32 МБ
  • добавлен 23 сентября 2011 г.
Издательство InTech, 2008, -596 pp. Сборник статей The greedy algorithm is one of the simplest approaches to solve the optizmization problem in which we want to determine the global optimum of a given function by a sequence of steps where at each stage we can make a choice among a class of possible decisions. In the greedy method the choice of the optimal decision is made on the information at hand without worrying about the effect these decisio...

Bogdanov A., Trevisan L. Average-Case Complexity

  • формат pdf
  • размер 737.3 КБ
  • добавлен 05 октября 2011 г.
Computing Research Repository, 2008, -81 pp. We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect...

Goldreich O. Computational Complexity. A Conceptual Perspective

  • формат pdf
  • размер 3.3 МБ
  • добавлен 31 октября 2011 г.
Издательство Cambridge University Press, 2008, -632 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Goldreich O. P, NP, and NP-Completeness. The Basics of Computational Complexity

  • формат pdf
  • размер 1.11 МБ
  • добавлен 31 октября 2011 г.
Издательство Cambridge University Press, 2010, -216 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Hopcroft John E., Motwani Rajeev, Ullman Jeffrey D. Introduction to Automata Theory, Languages, and Computation (2nd Edition)

  • формат djvu
  • размер 8.64 МБ
  • добавлен 29 марта 2011 г.
This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications.

Kozen D.C. Theory of Computation

  • формат pdf
  • размер 2.75 МБ
  • добавлен 08 декабря 2011 г.
Издательство Springer, 2006, -405 pp. The course serves a dual purpose: to cover core material in the foundations of computing for graduate students in computer science preparing for their PhD qualifying exams, and to provide an introduction to some more advanced topics in the theory of computational complexity for those intending to pursue further study in the area. The course is thus a mixture of core and advanced material. Most of the course...

Sipser Michael. Introduction to The Theory of Computation, Second Edition

  • формат djvu
  • размер 6.57 МБ
  • добавлен 30 октября 2009 г.
Книга профессора прикладной математики из Массачу?сетского технологи?ческого институ?та. Русского преревода, к сожалению, не существует (или я не нашел). Очень полезная книжка. В Маи по ней читаются лекции по Сппо. Michael Sipser Welcome! You are about to embark on the study of a fascinating and important subject. the theory of computation. It comprises the fundamental mathematical proper. ties of computer hardware, software, and certain applic...

Van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A. Algorithms and Complexity

  • формат djvu
  • размер 12.2 МБ
  • добавлен 11 мая 2011 г.
Издательсто Elsiever/MIT Press, 1990, -1010 pp. Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений Machine Models and Simulations A Catalog of Complexity Classes Machine-Independent Complexity Theory Kolmogorov Complexity and its Applications Data Structures Computational Geometry Algorithmic Motion Planning in Robotics Average-Case Analysis of Algorithms and Data Structures Graph Algorithms Algorithms in Number Theory...

Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

  • формат pdf
  • размер 2.31 МБ
  • добавлен 20 сентября 2011 г.
Издательство Springer, 2005, -306 pp. Complexity theory – is it a discipline for theoreticians who have no concern for the real world or a central topic of modern computer science? In this introductory text, complexity theory is presented as an active area of computer science with results that have implications for the development and use of algorithms. Our study will lead to insights into the structure of important optimization problems and wil...