PirateBay Download | davis m computability complexity languages 1983

davis m computability complexity languages 1983

Type:: E-books
Files:: 2
Size:: 11.8 MB
Uploaded On:: Dec. 7, 2022, 5:09 p.m.
Added By:: andryold1
Seeders:: 2
Leechers:: 0
Info Hash:: EEAE2BD5300439998C63707E93326F76D28A0E90

Textbook in PDF and DJVU formats Theoretical computer science is the mathematical study of models of computation. As such, it originated in the 1930s, well before the existence of modern computers, in the work of the logicians Church, Godel, Kleene, Post, and Turing. This early work has had a profound influence on the practical and theoretical development of computer science. Not only has the Turing-machine model proved basic for theory, but the work of these pioneers presaged many aspects of computational practice that are now commonplace and whose intellectual antecedents are typically unknown to users. Included among these are the existence in principle of all-purpose (or universal) digital computers, the concept of a program as a list of instructions in a formal 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 technological advances that have been taking place, important work in the foundations 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 science for undergraduate and graduate students that is sufficiently comprehensive that the professional literature of treatises and research papers will become accessible to our readers. We are dealing with a very young field that is still finding itself. Computer scientists have by no means been unanimous in judging which parts of the subject will turn out to have enduring significance. In this situation, fraught with peril for authors, we have attempted to select topics that have already achieved a polished classic form, and that we believe will play an important role in future research. We have assumed that many of our readers will have had little experience with mathematical proof, but that almost all of them have had substantial programming experience. Thus the first chapter contains an introduction to the use of proofs in mathematics in addition to the usual explanation of terminology and notation. We then proceed to take advantage of the reader's background by developing computability theory in the context of an extremely simple abstract programming language. By systematic use of a macro expansion technique, the surprising power of the language is demonstrated. This culminates in a universal program, which is written in all detail on a single page. By a series of simulations, we then obtain the equivalence of various different formulations of computability, including Turing's. Our point of view with respect to these simulations is that it should not be the reader's responsibility, at this stage, to fill in the details of vaguely sketched arguments, but rather that it is our responsibility as authors to arrange matters so that the simulations can be exhibited simply, clearly, and completely. Preliminaries Part 1 Computability Programs and Computable Functions Primitive Recursive Functions A Universal Program Calculations on Strings Turing Machines Processes and Grammars Part 2 Grammars and Automata Regular Languages Context-Free Languages Context-Sensitive Languages Part 3 Logic Propositional Calculus Quantification Theory Part 4 Complexity Loop Programs Abstract Complexity Polynomial-Time Computability Part 5 Unsolvability Classifying Unsolvable Problems Degrees of Unsolvability and Post's Problem

Get This Torrent

Davis M. Computability, Complexity, and Languages 1983.djvu 2.5 MB
Davis M. Computability, Complexity, and Languages 1983.pdf 9.4 MB

Details for: Davis M. Computability, Complexity, and Languages 1983

davis m computability complexity languages 1983

Similar Posts: