Mathematical Theory of Computation (Mcgraw-Hill Computer Science Series) [Hardcover]

Zohar Manna (Author)

Book Description

ISBN-10: 0070399107 | ISBN-13: 978-0070399105 | Publication Date: November 1974

With the objective of making into a science the art of verifying computer programs (debugging), the author addresses both practical and theoretical aspects. Subjects include computability (with discussions of finite automata and Turing machines); predicate calculus; verification of programs (bloth flowchart and algol-like programs); flowchart schemas; and the fixpoint theory of programs. 1974 edition. Includes 77 figures.

--This text refers to the Paperback edition.

Product Details

• Hardcover: 448 pages
• Publisher: Mcgraw-Hill College (November 1974)
• Language: English
• ISBN-10: 0070399107
• ISBN-13: 978-0070399105
• Product Dimensions: 9.1 x 6 x 1.1 inches
• Shipping Weight: 1.7 pounds
• Average Customer Review: 5.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #2,295,048 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

7 of 9 people found the following review helpful:

5.0 out of 5 stars A Classic text, August 19, 2009

By 

Joe Celko (Austin, TX) - See all my reviews

This review is from: Mathematical Theory of Computation (Dover Books on Mathematics) (Paperback)

Are you old enough to remember when Structured Programming was controversial? Dijkstra wrote "The GOTO Considered Harmful" in CACM 1968. The letter was an explanation of why the GOTO was a dangerous programming construct in mathematical terms. The math has been refined over the decades and it lead to formal correctness proof of programming, optimizing compilers, encapsulation, etc. Today, you do structured programming without even thinking about it; modern languages don't even have a GOTO any more.

But back in those days, the "cowboy coders" bitched and moaned about these terrible restrictions of "goto-less programming" and being limited to modules with one entry and one exit point, etc. Remember back then programmers wrote "GO TO <destination>", where destination was a label variable, or "GOTO (i) label1, label2, label3" as well as the simple "GO TO <label constant somewhere in 100000 lines of code; find it yourself>" routinely. Nobody thought about IF-THEN-ELSE, CASE/SWITCH/SELECT or RETURN constructs. They did not use WHILE or UNTIL loops when a backward GO TO would do the job.

All this crap was just theory getting in the way of their practical solutions and fast code. Most programmers then did not have the math background to appreciate that Structured Programming is MUCH more than "goto-less programming" and that you can prove programs correct in the same way that you prove a theorem in any other branch of mathematics.

This book is one of the most complete books on this topic and should be at least a reference book if not read cover to cover by any programmer who wants to be more than a code monkey.

1 of 1 people found the following review helpful:

5.0 out of 5 stars A classic textbook on theory of computation, April 26, 2011

By 

Scott (Dubuque, IA) - See all my reviews

Amazon Verified Purchase

This review is from: Mathematical Theory of Computation (Dover Books on Mathematics) (Paperback)

This 1974 text by Professor Zohar Manna at Stanford is one of my all-time favorites, even though I'm not a computer scientist or even a modern programmer. I've read all of Chapters 1 on Computability, 2 on Predicate Logic, and 4 on Flowchart Schemas since last Aug 2010, all reasonably comprehensible to me and massively interesting for their own sake.

Very interesting Chapter 1 covered regular expressions and finite automata in Section 1-1 and then Turing machines in several of their aspects in Sections 1-2 thru 1-5, with good additions of some of the important work of Post.

I think Chapter 2 on first-order logic, a specialty of mine, was generally well done, and at the start of Section 2-1.3 on pp. 90-91, Professor Manna wrote the clearest explanation I've ever seen of the logical concepts of validity, non-validity, unsatisfiability, and satisfiability. Section 2-2 on Natural Deduction showed the various sets of introduction and elimination rules for that style of deduction very well, but Manna's many example proofs in that section were not in that natural deduction style. Section 2-3 on the important resolution procedure was thorough, but it became very abstract near the end, i.e., not closing the deal very well.

Chapter 4 on Flowchart Schemas was a great look at this theoretical way of considering computation in general. Many kinds of schemata and their decision procedures were discussed thru Section 4-2. Then Section 4-3 on Formalization in Predicate Calculus rolled a lot of the methods of Section 2-1 into formalizing flowchart schemas. Difficult, but very interesting to read. Section 4-4 on Translation Problems was a highly difficult discussion of flowchart schema programs vs. recursive programs.

Chapter 5 on The Fixpoint Theory of Programs looks fascinating, but that chapter is more difficult than I am willing to try reading. Omitted Chapter 3 on Verification of Programs (via flowcharts) was the most heavily applied chapter and looked rather tedious to read, so I skipped it.

For those interested, at end of each chapter are very many problems to work.

In 2010, Zohar Manna and Aaron Bradley wrote a new book on similar subjects, especially logic and decision procedures, which I also have. Here is the link: The Calculus of Computation: Decision Procedures with Applications to Verification. For most of 2011, I also had a review of that book in Amazon.