Formal models of computation. The ultimate limits of computing
type: Item
instance of: scholarly article
zbMATH Open document ID: 0973.68069
author: Arthur Fleck
publication date: 2001-02-20T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D99
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 1566812
zbMATH Keywords: computational models
zbMATH Keywords: Turing machines
zbMATH Keywords: context-free grammars
MaRDI profile type: Publication
title: Formal models of computation. The ultimate limits of computing
published in: AMAST Series in Computing
review text: 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 understan…
reviewed by: Christina Diakaki
description: scientific article