Formal models of computation. The ultimate limits of computing (Q2701761)

The prime purpose of this book is to develop an understanding of the ultimate and insurmountable limits of computing. The boundaries of what is possible are explored for a variety of combinations of computing resources. To this end, a varied collection of computational models is considered at a high level of abstraction to ensure that the presented analysis applies to any suitable ``computer''. One of the features of the book is that in addition to the most familiar models, it also introduces a number of variations and applications in order to deepen the understanding and to keep the reader's motivation at a high level.NEWLINENEWLINENEWLINEUsually, the books that deal with this subject follow one of two approaches. The first approach is to start with the most general models such as the Turing machines, and proceed through a series of restrictions on available resources and capabilities to simpler and simpler models studying this way the reduction in the limits of computations that result. The second approach does the exactly opposite. It starts with the simplest model, namely the finite state machine, and considers a series of extensions of the computational resources and capabilities and the resulting expansions in computational power. This second approach is followed by the book, which consists of three main parts. According to the followed presentation approach, the first part is devoted to the finite state paradigm including regular expressions and acceptors, properties of regular languages, and transducers and other variations. The second part is devoted to the context-free grammars and automata, while the third and last part of the book is devoted to general computability models including context-sensitive languages, Turing machines and computability, and the universal machine and the impossible computations. The book includes also an introductory chapter in which the author provides a review of the mathematical prerequisites that the reader needs to understand in order to assimilate the presented ideas.NEWLINENEWLINENEWLINEThe background assumed of the reader includes some general knowledge and experience with computers and programming. As such, the book is well addressed to advanced undergraduate and graduate students, and researchers with an experience and an interest for further deepening into the ideas of computer science.