Computability and Unsolvability

ISBN-10: 0486614719

ISBN-13: 9780486614717

Edition: 1982 (Reprint)

Authors: Martin Davis

List price: $16.95 Buy it from $3.94
eBook available
30 day, 100% satisfaction guarantee

If an item you ordered from TextbookRush does not meet your expectations due to an error on our part, simply fill out a return request and then return it by mail within 30 days of ordering it for a full refund of item cost.

Learn more about our returns policy


Classic text considers general theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.
Used Starting from $3.94
New Starting from $14.84
eBooks Starting from $16.95
Buy eBooks
what's this?
Rush Rewards U
Members Receive:
You have reached 400 XP and carrot coins. That is the daily max!
Study Briefs

Limited time offer: Get the first one free! (?)

All the information you need in one place! Each Study Brief is a summary of one specific subject; facts, figures, and explanations to help you learn faster.

Add to cart
Study Briefs
Calculus 1 Online content $4.95 $1.99
Add to cart
Study Briefs
Algebra Online content $4.95 $1.99
Add to cart
Study Briefs
Introduction to Logic Online content $4.95 $1.99
Add to cart
Study Briefs
Business Math Formulas Online content $4.95 $1.99
Customers also bought

Book details

List price: $16.95
Copyright year: 1982
Publisher: Dover Publications, Incorporated
Publication date: 12/1/1985
Binding: Paperback
Pages: 288
Size: 5.50" wide x 8.50" long x 0.50" tall
Weight: 0.638
Language: English

Preface to the Dover Edition
Preface to the First Edition
Glossary of special symbols Introduction
Heuristic Remarks on Decision Problems
Suggestions to the Reader
Notational Conventions
The general theory of computability
Computable Functions
Turing Machines
Computable Functions and Partially Computable functions
Some Examples
Relatively Computable functions
Operations on Computable Functions
Preliminary Lemmas
Composition and Minimalization
Recursive functions
Some Classes of Functions
Finite Sequences of Natural Numbers
Primitive Recursion
Primitive Recursive functions
Recursive Sets and Predicates
Turing Machines Self-applied
Arithmetization of the Theory of Turing Machines
Computability and Recursiveness
A Universal Turing Machine
Unsolvable Decision Problems
Semicomputable Predicates
Decision Problems
Properties of Semicomputable Predicates
Recursively enumerable Sets
Two Recursively enumerable Sets
A Set Which Is Not Recursively Enumerable
Applications of the General Theory
Combinatorial Problems
Combinatorial systems
Turing machines and Semi-Thue Systems
Thue Systems
The Word Problem for Semigroups
Normal Systems and Post Systems
Diophantine Equations
Hilbert's Tenth Problem
Arithmetical and Diophantine Predicates
Arithmetical Representation of Semicomputable Predicates
Mathematical Logic
Incompleteness and Unsolvability Theorems for Logics
Arithmetical Logics
First-order Logics
Partial Propositional Calculi
Further Development of the General Theory
The Kleene Hierarchy
The Interation Theorem
Some First Applications of the Iteration Theorem
Predicates, Sets, and Functions
Strong Reducibility
Some Classes of Predicates
A Representation Theorem for P subscript 2 superscript A
Post's Representation Theorem
Computable Functionals
Complete Computable functionals
Normal Form Theorems
Partially Computable and Computable Functionals
Functionals and Relative Recursiveness
Decision Problems
The Recursion Theorems
The Classification of Unsolvable Decision Problems
Reducibility and the Kleene Hierarchy
Creative Sets and Simple Sets
Constructive Ordinals
Extensions of the Kleene Hierarchy
Some Results from the Elementary Theory of Numbers
Hilbert's Tenth Problem is Unsolvable
Free shipping on orders over $35*

*A minimum purchase of $35 is required. Shipping is provided via FedEx SmartPost® and FedEx Express Saver®. Average delivery time is 1 – 5 business days, but is not guaranteed in that timeframe. Also allow 1 - 2 days for processing. Free shipping is eligible only in the continental United States and excludes Hawaii, Alaska and Puerto Rico. FedEx service marks used by permission."Marketplace" orders are not eligible for free or discounted shipping.

Learn more about the TextbookRush Marketplace.