In Pursuit of the Traveling Salesman

Author: William J. Cook
Publisher: Princeton University Press
ISBN: 0691163529
Category : Mathematics
Languages : en
Pages : 244

Book Description
The story of one of the greatest unsolved problems in mathematics What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics—and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today’s state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets. In Pursuit of the Traveling Salesman travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.

Introduction to the Theory of Computation

Author: Michael Sipser
Publisher: Thomson/Course Technology
ISBN: 9780619217648
Category : Computational complexity
Languages : en
Pages : 437

Book Description
"Intended as an upper-level undergraduate or introductory graduate text in computer science theory," this book lucidly covers the key concepts and theorems of the theory of computation. The presentation is remarkably clear; for example, the "proof idea," which offers the reader an intuitive feel for how the proof was constructed, accompanies many of the theorems and a proof. Introduction to the Theory of Computation covers the usual topics for this type of text plus it features a solid section on complexity theory--including an entire chapter on space complexity. The final chapter introduces more advanced topics, such as the discussion of complexity classes associated with probabilistic algorithms.

Discrete Structures, Logic, and Computability

Author: James L. Hein
Publisher: Jones & Bartlett Learning
ISBN: 9780763718435
Category : Computers
Languages : en
Pages : 976

Book Description
Discrete Structure, Logic, and Computability introduces the beginning computer science student to some of the fundamental ideas and techniques used by computer scientists today, focusing on discrete structures, logic, and computability. The emphasis is on the computational aspects, so that the reader can see how the concepts are actually used. Because of logic's fundamental importance to computer science, the topic is examined extensively in three phases that cover informal logic, the technique of inductive proof; and formal logic and its applications to computer science.

Decidability of Logical Theories and Their Combination

Author: João Rasga
Publisher: Springer Nature
ISBN: 3030565548
Category : Mathematics
Languages : en
Pages : 185

Book Description
This textbook provides a self-contained introduction to decidability of first-order theories and their combination. The technical material is presented in a systematic and universal way and illustrated with plenty of examples and a range of proposed exercises. After an overview of basic first-order logic concepts, the authors discuss some model-theoretic notions like embeddings, diagrams, and elementary substructures. The text then goes on to explore an applicable way to deduce logical consequences from a given theory and presents sufficient conditions for a theory to be decidable. The chapters that follow focus on quantifier elimination, decidability of the combination of first-order theories and the basics of computability theory. The inclusion of a chapter on Gentzen calculus, cut elimination, and Craig interpolation, as well as a chapter on combination of theories and preservation of decidability, help to set this volume apart from similar books in the field. Decidability of Logical Theories and their Combination is ideal for graduate students of Mathematics and is equally suitable for Computer Science, Philosophy and Physics students who are interested in gaining a deeper understanding of the subject. The book is also directed to researchers that intend to get acquainted with first-order theories and their combination.

Computability

Author: Nigel Cutland
Publisher: Cambridge University Press
ISBN: 9780521294652
Category : Computers
Languages : en
Pages : 268

Book Description
What can computers do in principle? What are their inherent theoretical limitations? The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function - a function whose values can be calculated in an automatic way.

Turing Computability

Author: Robert I. Soare
Publisher: Springer
ISBN: 3642319335
Category : Computers
Languages : en
Pages : 289

Book Description
Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic. The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which all mathematicians recognize in their subject. Part I gives a thorough development of the foundations of computability, from the definition of Turing machines up to finite injury priority arguments. Key topics include relative computability, and computably enumerable sets, those which can be effectively listed but not necessarily effectively decided, such as the theorems of Peano arithmetic. Part II includes the study of computably open and closed sets of reals and basis and nonbasis theorems for effectively closed sets. Part III covers minimal Turing degrees. Part IV is an introduction to games and their use in proving theorems. Finally, Part V offers a short history of computability theory. The author has honed the content over decades according to feedback from students, lecturers, and researchers around the world. Most chapters include exercises, and the material is carefully structured according to importance and difficulty. The book is suitable for advanced undergraduate and graduate students in computer science and mathematics and researchers engaged with computability and mathematical logic.

Elements of Computation Theory

Author: Arindama Singh
Publisher: Springer Science & Business Media
ISBN: 1848824971
Category : Computers
Languages : en
Pages : 429

Book Description
The foundation of computer science is built upon the following questions: What is an algorithm? What can be computed and what cannot be computed? What does it mean for a function to be computable? How does computational power depend upon programming constructs? Which algorithms can be considered feasible? For more than 70 years, computer scientists are searching for answers to such qu- tions. Their ingenious techniques used in answering these questions form the theory of computation. Theory of computation deals with the most fundamental ideas of computer s- ence in an abstract but easily understood form. The notions and techniques employed are widely spread across various topics and are found in almost every branch of c- puter science. It has thus become more than a necessity to revisit the foundation, learn the techniques, and apply them with con?dence. Overview and Goals This book is about this solid, beautiful, and pervasive foundation of computer s- ence. It introduces the fundamental notions, models, techniques, and results that form the basic paradigms of computing. It gives an introduction to the concepts and mathematics that computer scientists of our day use to model, to argue about, and to predict the behavior of algorithms and computation. The topics chosen here have shown remarkable persistence over the years and are very much in current use.

A Primer on Determinism

Author: John Earman
Publisher: Springer Science & Business Media
ISBN: 9789027722409
Category : Mathematics
Languages : en
Pages : 298

Book Description
The title of this work is to be taken seriously: it is a small book for teaching students to read the language of determinism. Some prior knowledge of college-level mathematics and physics is presupposed, but otherwise the book is suitable for use in an advanced undergraduate or beginning graduate course in the philosophy of science. While writing I had in mind primarily a philosophical audience, but I hope that students and colleagues from the sciences will also find the treatment of scientific issues of interest. Though modest in not trying to reach beyond an introductory level of analysis, the work is decidedly immodest in trying to change a number of misimpressions that pervade the philosophical literature. For example, when told that classical physics is not the place to look for clean and unproblematic examples of determinism, most philosophers react with a mixture of disbelief and incomprehension. The misconcep tions on which that reaction is based can and must be changed.

Three Views of Logic

Author: Donald W. Loveland
Publisher: Princeton University Press
ISBN: 140084875X
Category : Mathematics
Languages : en
Pages : 344

Book Description
Demonstrating the different roles that logic plays in the disciplines of computer science, mathematics, and philosophy, this concise undergraduate textbook covers select topics from three different areas of logic: proof theory, computability theory, and nonclassical logic. The book balances accessibility, breadth, and rigor, and is designed so that its materials will fit into a single semester. Its distinctive presentation of traditional logic material will enhance readers' capabilities and mathematical maturity. The proof theory portion presents classical propositional logic and first-order logic using a computer-oriented (resolution) formal system. Linear resolution and its connection to the programming language Prolog are also treated. The computability component offers a machine model and mathematical model for computation, proves the equivalence of the two approaches, and includes famous decision problems unsolvable by an algorithm. The section on nonclassical logic discusses the shortcomings of classical logic in its treatment of implication and an alternate approach that improves upon it: Anderson and Belnap's relevance logic. Applications are included in each section. The material on a four-valued semantics for relevance logic is presented in textbook form for the first time. Aimed at upper-level undergraduates of moderate analytical background, Three Views of Logic will be useful in a variety of classroom settings. Gives an exceptionally broad view of logic Treats traditional logic in a modern format Presents relevance logic with applications Provides an ideal text for a variety of one-semester upper-level undergraduate courses

Sets, Logic, Computation

Author: Richard Zach
Publisher:
ISBN:
Category :
Languages : en
Pages : 418

Book Description
A textbook on the semantics, proof theory, and metatheory of first-order logic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. It is based on the Open Logic project, and available for free download at slc.openlogicproject.org.