Buy What Can Be Computed? by John MacCormick - Bookswagon
close menu
Bookswagon
search
My Account
Home > Computer Science Books > What Can Be Computed?: A Practical Guide to the Theory of Computation
What Can Be Computed?: A Practical Guide to the Theory of Computation

What Can Be Computed?: A Practical Guide to the Theory of Computation


     0     
5
4
3
2
1



Available


X
About the Book

An accessible and rigorous textbook for introducing undergraduates to computer science theory What Can Be Computed? is a uniquely accessible yet rigorous introduction to the most profound ideas at the heart of computer science. Crafted specifically for undergraduates who are studying the subject for the first time, and requiring minimal prerequisites, the book focuses on the essential fundamentals of computer science theory and features a practical approach that uses real computer programs (Python and Java) and encourages active experimentation. It is also ideal for self-study and reference. The book covers the standard topics in the theory of computation, including Turing machines and finite automata, universal computation, nondeterminism, Turing and Karp reductions, undecidability, time-complexity classes such as P and NP, and NP-completeness, including the Cook-Levin Theorem. But the book also provides a broader view of computer science and its historical development, with discussions of Turing's original 1936 computing machines, the connections between undecidability and Goedel's incompleteness theorem, and Karp's famous set of twenty-one NP-complete problems. Throughout, the book recasts traditional computer science concepts by considering how computer programs are used to solve real problems. Standard theorems are stated and proven with full mathematical rigor, but motivation and understanding are enhanced by considering concrete implementations. The book's examples and other content allow readers to view demonstrations of-and to experiment with-a wide selection of the topics it covers. The result is an ideal text for an introduction to the theory of computation. An accessible and rigorous introduction to the essential fundamentals of computer science theory, written specifically for undergraduates taking introduction to the theory of computation Features a practical, interactive approach using real computer programs (Python in the text, with forthcoming Java alternatives online) to enhance motivation and understanding Gives equal emphasis to computability and complexity Includes special topics that demonstrate the profound nature of key ideas in the theory of computation Lecture slides and Python programs are available at whatcanbecomputed.com



Table of Contents:
  • Acknowledgments
  • Preface for instructors
    • The inspiration of GEB
    • Which “theory” course are we talking about?
    • The features that might make this book appealing
    • What’s in and what’s out
    • Possible courses based on this book
    • Computer science as a liberal art
  • OVERVIEW
    • 1 INTRODUCTION: WHAT CAN AND CANNOT BE COMPUTED?
      • 1.1 Tractable problems
      • 1.2 Intractable problems
      • 1.3 Uncomputable problems
      • 1.4 A more detailed overview of the book
        • Overview of part I: Computability theory
        • Overview of part II: Complexity theory
        • Overview of part III: Origins and applications
      • 1.5 Prerequisites for understanding this book
      • 1.6 The goals of the book
        • The fundamental goal: What can be computed?
        • Secondary goal 1: A practical approach
        • Secondary goal 2: Some historical insight
      • 1.7 Why study the theory of computation?
        • Reason 1: The theory of computation is useful
        • Reason 2: The theory of computation is beautiful and important
        • Exercises
  • Part I: COMPUTABILITY THEORY
    • 2 WHAT IS A COMPUTER PROGRAM?
      • 2.1 Some Python program basics
        • Editing and rerunning a Python program
        • Running a Python program on input from a file
        • Running more complex experiments on Python programs
      • 2.2 SISO Python programs
        • Programs that call other functions and programs
      • 2.3 ASCII characters and multiline strings
      • 2.4 Some problematic programs
      • 2.5 Formal definition of Python program
      • 2.6 Decision programs and equivalent programs
      • 2.7 Real-world programs versus SISO Python programs
        • Exercises
    • 3 SOME IMPOSSIBLE PYTHON PROGRAMS
      • 3.1 Proof by contradiction
      • 3.2 Programs that analyze other programs
        • Programs that analyze themselves
      • 3.3 The program yesOnString.py
      • 3.4 The program yesOnSelf.py
      • 3.5 The program notYesOnSelf.py
      • 3.6 yesOnString.py can’t exist either
        • A compact proof that yesOnString.py can’t exist
      • 3.7 Perfect bug-finding programs are impossible
      • 3.8 We can still find bugs, but we can’t do it perfectly
        • Exercises
    • 4 WHAT IS A COMPUTATIONAL PROBLEM?
      • 4.1 Graphs, alphabets, strings, and languages
        • Graphs
        • Trees and rooted trees
        • Alphabets
        • Strings
        • Languages
      • 4.2 Defining computational problems
        • Positive and negative instances
        • Notation for computational problems
      • 4.3 Categories of computational problems
        • Search problems
        • Optimization problems
        • Threshold problems
        • Function problems
        • Decision problems
        • Converting between general and decision problems
        • Complement of a decision problem
        • Computational problems with two input strings
      • 4.4 The formal definition of “solving” a problem
        • Computable functions
      • 4.5 Recognizing and deciding languages
        • Recognizable languages
        • Recursive and recursively enumerable languages
        • Exercises
    • 5 TURING MACHINES: THE SIMPLEST COMPUTERS
      • 5.1 Definition of a Turing machine
        • Halting and looping
        • Accepters and transducers
        • Abbreviated notation for state diagrams
        • Creating your own Turing machines
      • 5.2 Some nontrivial Turing machines
        • The moreCsThanGs machine
        • The countCs machine
        • Important lessons from the countCs example
      • 5.3 From single-tape Turing machines to multi-tape Turing machines
        • Two-tape, single-head Turing machines
        • Two-way infinite tapes
        • Multi-tape, single-head Turing machines
        • Two-tape, two-head Turing machines
      • 5.4 From multi-tape Turing machines to Python programs and beyond
        • Multi-tape Turing machine → random-access Turing machine
        • Random-access Turing machine → real computer
        • Modern computer → Python program
      • 5.5 Going back the other way: Simulating a Turing machine with Python
        • A serious caveat: Memory limitations and other technicalities
      • 5.6 Classical computers can simulate quantum computers
      • 5.7 All known computers are Turing equivalent
        • Exercises
    • 6 UNIVERSAL COMPUTER PROGRAMS: PROGRAMS THAT CAN DO ANYTHING
      • 6.1 Universal Python programs
      • 6.2 Universal Turing machines
      • 6.3 Universal computation in the real world
      • 6.4 Programs that alter other programs
        • Ignoring the input and performing a fixed calculation instead
      • 6.5 Problems that are undecidable but recognizable
        • Exercises
    • 7 REDUCTIONS: HOW TO PROVE A PROBLEM IS HARD
      • 7.1 A reduction for easiness
      • 7.2 A reduction for hardness
      • 7.3 Formal definition of Turing reduction
        • Why “Turing” reduction?
        • Oracle programs
        • Why is ≤T used to denote a Turing reduction?
        • Beware the true meaning of “reduction”
      • 7.4 Properties of Turing reductions
      • 7.5 An abundance of uncomputable problems
        • The variants of YESONSTRING
        • The halting problem and its variants
        • Uncomputable problems that aren’t decision problems
      • 7.6 Even more uncomputable problems
        • The computational problem COMPUTESF
        • Rice’s theorem
      • 7.7 Uncomputable problems that aren’t about programs
      • 7.8 Not every question about programs is uncomputable
      • 7.9 Proof techniques for uncomputability
        • Technique 1: The reduction recipe
        • Technique 2: Reduction with explicit Python programs
        • Technique 3: Apply Rice’s theorem
        • Exercises
    • 8 NONDETERMINISM: MAGIC OR REALITY?
      • 8.1 Nondeterministic Python programs
      • 8.2 Nondeterministic programs for nondecision problems
      • 8.3 Computation trees
      • 8.4 Nondeterminism doesn’t change what is computable
      • 8.5 Nondeterministic Turing machines
      • 8.6 Formal definition of nondeterministic Turing machines
      • 8.7 Models of nondeterminism
      • 8.8 Unrecognizable problems
      • 8.9 Why study nondeterminism?
        • Exercises
    • 9 FINITE AUTOMATA: COMPUTING WITH LIMITED RESOURCES
      • 9.1 Deterministic finite automata
      • 9.2 Nondeterministic finite automata
        • State diagrams for nfas
        • Formal definition of an nfa
        • How does an nfa accept a string?
        • Sometimes nfas make things easier
      • 9.3 Equivalence of nfas and dfas
        • Nondeterminism can affect computability: The example of pdas
        • Practicality of converted nfas
        • Minimizing the size of dfas
      • 9.4 Regular expressions
        • Pure regular expressions
        • Standard regular expressions
        • Converting between regexes and finite automata
      • 9.5 Some languages aren’t regular
        • The nonregular language GnTn
        • The key difference between Turing machines and finite automata
      • 9.6 Many more nonregular languages
        • The pumping lemma
      • 9.7 Combining regular languages
        • Exercises
  • Part II: COMPUTATIONAL COMPLEXITY THEORY
    • 10 COMPLEXITY THEORY: WHEN EFFICIENCY DOES MATTER
      • 10.1 Complexity theory uses asymptotic running times
      • 10.2 Big-O notation
        • Dominant terms of functions
        • A practical definition of big-O notation
        • Superpolynomial and subexponential
        • Other asymptotic notation
        • Composition of polynomials is polynomial
        • Counting things with big-O
      • 10.3 The running time of a program
        • Running time of a Turing machine
        • Running time of a Python program
        • The lack of rigor in Python running times
      • 10.4 Fundamentals of determining time complexity
        • A crucial distinction: The length of the input versus the numerical value of the input
        • The complexity of arithmetic operations
        • Beware of constant-time arithmetic operations
        • The complexity of factoring
        • The importance of the hardness of factoring
        • The complexity of sorting
      • 10.5 For complexity, the computational model does matter
        • Simulation costs for common computational models
        • Multi-tape simulation has quadratic cost
        • Random-access simulation has cubic cost
        • Universal simulation has logarithmic cost
        • Real computers cost only a constant factor
        • Python programs cost the same as real computers
        • Python programs can simulate random-access Turing machines efficiently
        • Quantum simulation may have exponential cost
        • All classical computational models differ by only polynomial factors
        • Our standard computational model: Python programs
      • 10.6 Complexity classes
        • Exercises
    • 11 Poly AND Expo: THE TWO MOST FUNDAMENTAL COMPLEXITY CLASSES
      • 11.1 Definitions of Poly and Expo
        • Poly and Expo compared to P, Exp, and FP
      • 11.2 Poly is a subset of Expo
      • 11.3 A first look at the boundary between Poly and Expo
        • ALL3SETS and ALLSUBSETS
        • Traveling salespeople and shortest paths
        • Multiplying and factoring
        • Back to the boundary between Poly and Expo
        • Primality testing is in Poly
      • 11.4 Poly and Expo don’t care about the computational model
      • 11.5 HALTEx: A decision problem in Expo but not Poly
      • 11.6 Other problems that are outside Poly
      • 11.7 Unreasonable encodings of the input affect complexity
      • 11.8 Why study Poly, really?
        • Exercises
    • 12 PolyCheck AND NPoly: HARD PROBLEMS THAT ARE EASY TO VERIFY
      • 12.1 Verifiers
        • Why “unsure”?
      • 12.2 Polytime verifiers
        • Bounding the length of proposed solutions and hints
        • Verifying negative instances in exponential time
        • Solving arbitrary instances in exponential time
      • 12.3 The complexity class PolyCheck
        • Some PolyCheck examples: PACKING,SUBSETSUM, and PARTITION
        • The haystack analogy for PolyCheck
      • 12.4 The complexity class NPoly
      • 12.5 PolyCheck and NPoly are identical
        • Every PolyCheck problem is in NPoly
        • Every NPoly problem is in PolyCheck
      • 12.6 The PolyCheck/NPoly sandwich
      • 12.7 Nondeterminism does seem to change what is computable efficiently
      • 12.8 The fine print about NPoly
        • An alternative definition of NPoly
        • NPoly compared to NP and FNP
        • Exercises
    • 13 POLYNOMIAL-TIME MAPPING REDUCTIONS: PROVING X IS AS EASY AS Y
      • 13.1 Definition of polytime mapping reductions
        • Polyreducing to nondecision problems
      • 13.2 The meaning of polynomial-time mapping reductions
      • 13.3 Proof techniques for polyreductions
      • 13.4 Examples of polyreductions using Hamilton cycles
        • A polyreduction from UHC to DHC
        • A polyreduction from DHC to UHC
      • 13.5 Three satisfiability problems: CIRCUITSAT, SAT, and 3-SAT
        • Why do we study satisfiability problems?
        • CIRCUITSAT
        • SAT
        • Conjunctive normal form
        • ASCII representation of Boolean formulas
        • 3-SAT
      • 13.6 Polyreductions between CIRCUITSAT, SAT, and 3-SAT
        • The Tseytin transformation
      • 13.7 Polyequivalence and its consequences
        • Exercises
    • 14 NP-COMPLETENESS: MOST HARD PROBLEMS ARE EQUALLY HARD
      • 14.1 P versus NP
      • 14.2 NP-completeness
        • Reformulations of P versus NP using NP-completeness
      • 14.3 NP-hardness
      • 14.4 Consequences of P=NP
      • 14.5 CIRCUITSAT is a “hardest” NP problem
      • 14.6 NP-completeness is widespread
      • 14.7 Proof techniques for NP-completeness
      • 14.8 The good news and bad news about NP-completeness
        • Problems in NPoly but probably not NP-hard
        • Some problems that are in P
        • Some NP-hard problems can be approximated efficiently
        • Some NP-hard problems can be solved efficiently for real-world inputs
        • Some NP-hard problems can be solved in pseudo-polynomial time
        • Exercises
  • Part III: ORIGINS AND APPLICATIONS
    • 15 THE ORIGINAL TURING MACHINE
      • 15.1 Turing’s definition of a “computing machine”
      • 15.2 Machines can compute what humans can compute
      • 15.3 The Church–Turing thesis: A law of nature?
        • The equivalence of digital computers
        • Church’s thesis: The equivalence of computer programs and algorithms
        • Turing’s thesis: The equivalence of computer programs and human brains
        • Church–Turing thesis: The equivalence of all computational processes
        • Exercises
    • 16 YOU CAN’T PROVE EVERYTHING THAT’S TRUE
      • The history of computer proofs
      • 16.1 Mechanical proofs
        • Semantics and truth
        • Consistency and completeness
        • Decidability of logical systems
      • 16.2 Arithmetic as a logical system
        • Converting the halting problem to a statement about integers
        • Recognizing provable statements about integers
        • The consistency of Peano arithmetic
      • 16.3 The undecidability of mathematics
      • 16.4 The incompleteness of mathematics
      • 16.5 What have we learned and why did we learn it?
        • Exercises
    • 17 KARP’S 21 PROBLEMS
      • 17.1 Karp’s overview
      • 17.2 Karp’s definition of NP-completeness
      • 17.3 The list of 21 NP-complete problems
      • 17.4 Reductions between the 21 NP-complete problems
        • Polyreducing SAT to CLIQUE
        • Polyreducing CLIQUE to NODE COVER
        • Polyreducing DHC to UHC
        • Polyreducing SAT to 3-SAT
        • Polyreducing KNAPSACK to PARTITION
      • 17.5 The rest of the paper: NP-hardness and more
        • Exercises
    • 18 CONCLUSION: WHAT WILL BE COMPUTED?
      • 18.1 The big ideas about what can be computed
  • Bibliography
  • Index


About the Author :

John MacCormick is associate professor of computer science at Dickinson College and a leading teacher, researcher, and writer in his field. He has a PhD in computer vision from the University of Oxford and has worked in the research labs of Hewlett-Packard and Microsoft. His previous books include Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers (Princeton). Erik Demaine and Martin Demaine created the curved crease sculpture featured on the cover of What Can Be Computed? Cover photo courtesy of the artists.



Review :
"The concept is excellent, and it fills an important gap in the available textbooks on computation theory."---Kitty Meeks, London Mathematical Society


Best Sellers


Product Details
  • ISBN-13: 9780691170664
  • Publisher: Princeton University Press
  • Publisher Imprint: Princeton University Press
  • Height: 254 mm
  • No of Pages: 408
  • Sub Title: A Practical Guide to the Theory of Computation
  • Width: 178 mm
  • ISBN-10: 0691170665
  • Publisher Date: 01 May 2018
  • Binding: Hardback
  • Language: English
  • Returnable: 03
  • Weight: 998 gr

Related Categories

Similar Products

Add Photo
Add Photo

Customer Reviews

REVIEWS      0     
Click Here To Be The First to Review this Product
What Can Be Computed?: A Practical Guide to the Theory of Computation
Princeton University Press -
What Can Be Computed?: A Practical Guide to the Theory of Computation
Writing guidlines
We want to publish your review, so please:
  • keep your review on the product. Review's that defame author's character will be rejected.
  • Keep your review focused on the product.
  • Avoid writing about customer service. contact us instead if you have issue requiring immediate attention.
  • Refrain from mentioning competitors or the specific price you paid for the product.
  • Do not include any personally identifiable information, such as full names.

What Can Be Computed?: A Practical Guide to the Theory of Computation

Required fields are marked with *

Review Title*
Review
    Add Photo Add up to 6 photos
    Would you recommend this product to a friend?
    Tag this Book Read more
    Does your review contain spoilers?
    What type of reader best describes you?
    I agree to the terms & conditions
    You may receive emails regarding this submission. Any emails will include the ability to opt-out of future communications.

    CUSTOMER RATINGS AND REVIEWS AND QUESTIONS AND ANSWERS TERMS OF USE

    These Terms of Use govern your conduct associated with the Customer Ratings and Reviews and/or Questions and Answers service offered by Bookswagon (the "CRR Service").


    By submitting any content to Bookswagon, you guarantee that:
    • You are the sole author and owner of the intellectual property rights in the content;
    • All "moral rights" that you may have in such content have been voluntarily waived by you;
    • All content that you post is accurate;
    • You are at least 13 years old;
    • Use of the content you supply does not violate these Terms of Use and will not cause injury to any person or entity.
    You further agree that you may not submit any content:
    • That is known by you to be false, inaccurate or misleading;
    • That infringes any third party's copyright, patent, trademark, trade secret or other proprietary rights or rights of publicity or privacy;
    • That violates any law, statute, ordinance or regulation (including, but not limited to, those governing, consumer protection, unfair competition, anti-discrimination or false advertising);
    • That is, or may reasonably be considered to be, defamatory, libelous, hateful, racially or religiously biased or offensive, unlawfully threatening or unlawfully harassing to any individual, partnership or corporation;
    • For which you were compensated or granted any consideration by any unapproved third party;
    • That includes any information that references other websites, addresses, email addresses, contact information or phone numbers;
    • That contains any computer viruses, worms or other potentially damaging computer programs or files.
    You agree to indemnify and hold Bookswagon (and its officers, directors, agents, subsidiaries, joint ventures, employees and third-party service providers, including but not limited to Bazaarvoice, Inc.), harmless from all claims, demands, and damages (actual and consequential) of every kind and nature, known and unknown including reasonable attorneys' fees, arising out of a breach of your representations and warranties set forth above, or your violation of any law or the rights of a third party.


    For any content that you submit, you grant Bookswagon a perpetual, irrevocable, royalty-free, transferable right and license to use, copy, modify, delete in its entirety, adapt, publish, translate, create derivative works from and/or sell, transfer, and/or distribute such content and/or incorporate such content into any form, medium or technology throughout the world without compensation to you. Additionally,  Bookswagon may transfer or share any personal information that you submit with its third-party service providers, including but not limited to Bazaarvoice, Inc. in accordance with  Privacy Policy


    All content that you submit may be used at Bookswagon's sole discretion. Bookswagon reserves the right to change, condense, withhold publication, remove or delete any content on Bookswagon's website that Bookswagon deems, in its sole discretion, to violate the content guidelines or any other provision of these Terms of Use.  Bookswagon does not guarantee that you will have any recourse through Bookswagon to edit or delete any content you have submitted. Ratings and written comments are generally posted within two to four business days. However, Bookswagon reserves the right to remove or to refuse to post any submission to the extent authorized by law. You acknowledge that you, not Bookswagon, are responsible for the contents of your submission. None of the content that you submit shall be subject to any obligation of confidence on the part of Bookswagon, its agents, subsidiaries, affiliates, partners or third party service providers (including but not limited to Bazaarvoice, Inc.)and their respective directors, officers and employees.

    Accept

    Fresh on the Shelf


    Inspired by your browsing history


    Your review has been submitted!

    You've already reviewed this product!
    Your IP: 216.73.216.196 IN