Models of Computation: An Introduction to Computability Theory (Undergraduate Topics in Computer Science) [Paperback]

Maribel Fernandez (Author)

Book Description

Publication Date: May 29, 2009 | ISBN-10: 1848824335 | ISBN-13: 978-1848824331 | Edition: 1st Edition.

A Concise Introduction to Computation Models and Computability Theory provides an introduction to the essential concepts in computability, using several models of computation, from the standard Turing Machines and Recursive Functions, to the modern computation models inspired by quantum physics. An in-depth analysis of the basic concepts underlying each model of computation is provided. Divided into two parts, the first highlights the traditional computation models used in the first studies on computability: - Automata and Turing Machines; - Recursive functions and the Lambda-Calculus; - Logic-based computation models. and the second part covers object-oriented and interaction-based models. There is also a chapter on concurrency, and a final chapter on emergent computation models inspired by quantum mechanics. At the end of each chapter there is a discussion on the use of computation models in the design of programming languages.

Editorial Reviews

Review

From the reviews: "The focus of this relatively short book is on newer object-oriented and interaction-oriented models, including recent work in quantum computing and systems biology. … the book is designed for advanced undergraduate and graduate students. … Each chapter starts by clearly indicating what will be covered and ends with a series of exercises. … the book as a whole is extremely well written. Definitions are clearly stated … . Each model of computation is precisely defined, and the examples are clear and to the point." (K. Harrow, ACM Computing Reviews, September, 2009) “It is a pleasure to see a book which takes a different approach to computer theory. … This short book can be used for a one-term course … . A valuable primer for students of programming languages. Summing Up: Highly recommended. Upper-division undergraduates and graduate students.” (P. Cull, Choice, Vol. 47 (3), November, 2009)

From the Back Cover

An Introduction to Computability Theory provides an introduction to the essential concepts in computability, using several models of computation, from Turing machines to the modern computation models inspired by quantum physics. It is addressed to advanced undergraduate students, as a complement to programming courses, or to postgraduate students interested in foundations of computation and the theory of computability. There are two parts in the book. The first highlights the traditional models of computation used in the first studies on computability: - Automata and Turing Machines; - Recursive functions and the Lambda-Calculus; - Logic-based computation models. The second part covers object-oriented and interaction-based models, and includes a chapter on concurrency and a chapter on emergent models of computation inspired by quantum mechanics and systems biology. At the end of each chapter there is a list of exercises, solutions to selected exercises are provided in the final chapter of the book. The book gives an in-depth analysis of the basic concepts underlying each model of computation. It privileges the understanding of the basic techniques and their relationships over simply describing their properties.

Product Details

• Paperback: 196 pages
• Publisher: Springer; 1st Edition. edition (May 29, 2009)
• Language: English
• ISBN-10: 1848824335
• ISBN-13: 978-1848824331
• Product Dimensions: 9.1 x 6.9 x 0.6 inches
• Shipping Weight: 12.6 ounces (View shipping rates and policies)
• Average Customer Review: 3.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #2,279,139 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

0 of 1 people found the following review helpful:

3.0 out of 5 stars Short, but possibly too short, August 16, 2011

By 

Jacob - See all my reviews

This review is from: Models of Computation: An Introduction to Computability Theory (Undergraduate Topics in Computer Science) (Paperback)

About me: I'm a grad student in math, but have no prior experience
of the topic of the book. I have actually not yet read the 40
last pages or so, so the review is about the rest of the book.

I will be quite negative below, so I want to start by saying
that most chapters are OK, and I love short books. And this
book gives you a quick way of getting aquainted with various models
of computation. I dont agree with the official reviewer that
it goes in to depth or is extremely clear and well written.
On the contrary, it does NOT go into depth in all chapters, but
is rather uneven. I really liked the chapter about lambda-calculus.

My general impression is that the author is often saying
"how to think" about the definitions and concepts, and what they
intuitively are, rather than precisely saying what the definition IS.
I believe that the cause of my confusion, other than perhaps ignorance,
is the lack of crucial pieces of information. (See examples below).

Many times I found myself confused after reading a definition, and
really needed an example to clarify what was going on. Although
there are fairly many examples in the book, there were several places
in desperate need thereof.

It is mostly chapters 5 and 7 that I find confusing.

Example (chapter 5, on logic programs)
Definitive clauses - Program clauses and Goals - are defined.
A definitive clause is P1 or (not P2 or not P3 .... or not Pn), i.e. a
disjunction of so called "literals", and atmost one literal is positive.
A definitive clause is a Goal if we remove P1, i.e. we have only negative literals.

The problem is that there is only a definition of what a Goal is but not
what meeting a Goal is...
Only a very vague and incomplete explaination is given:

"Program clauses can be seen as defining a database: [...] Goals are questions
to be answered using the information about the problem in the database.
This can be better seen with some examples."

Then there is only ONE example in which the goal has only ONE negative literal.
That leaves the reader wondering if each literal P2, ...., Pn should be true
or just "atleast one of them".

Since the notation for a goal is :- P2,P3,...,Pn
you might believe that the goal is to deduce ALL of the Pi's, but
since its a disjunction of negative literals, mathematically it only makes sense
if the goal clause should be disproven, which means that ONE of the Pi's hold.
It gets even more confusing later on. Although I might have my self to blame
for some of the confusion, I am pretty convinced this is far from optimally
written.

Other complaints:
There are some flaws in the technique of writing. For example the author mentions
multisets several times, but gives the definition only the last time. On another
instance a new symbol is used and defined afterwards.
There is also a logical flaw on page 61. There is an argument that "bounded minimisation"
of a primitive recursive predicate is also primitive recursive.
The argument uses a lemma whose input are functions f_1, ..., f_k that are primitive recursive
total functions. Then the lemma is applied in a case where f_1 is a priori only partially defined.
I'm sure its possible to fix this argument, but it still makes life unneccesarily difficult for
the reader.