Understanding Computation : Pillars, Paradigms, Principles / by Arnold L. Rosenberg, Lenwood S. Heath.

Format:

Book

Author/Creator:

Rosenberg, Arnold L., Author.

Heath, Lenwood S., Author.

Contributor:

SpringerLink (Online service)

Series:

Computer Science (SpringerNature-11645)

Texts in computer science 1868-095X

Texts in Computer Science, 1868-095X

Language:

English

Subjects (All):

Computer science.

Theory of Computation.

Local Subjects:

Theory of Computation.

Physical Description:

1 online resource (XVII, 570 pages) : 87 illustrations

Edition:

1st ed. 2022.

Contained In:

Springer Nature eBook

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2022.

System Details:

text file PDF

Summary:

Computation theory is a discipline that uses mathematical concepts and tools to expose the nature of "computation" and to explain a broad range of computational phenomena: Why is it harder to perform some computations than others? Are the differences in difficulty that we observe inherent, or are they artifacts of the way we try to perform the computations? How does one reason about such questions? This unique textbook strives to endow students with conceptual and manipulative tools necessary to make computation theory part of their professional lives. The work achieves this goal by means of three stratagems that set its approach apart from most other texts on the subject. For starters, it develops the necessary mathematical concepts and tools from the concepts' simplest instances, thereby helping students gain operational control over the required mathematics. Secondly, it organizes development of theory around four "pillars," enabling students to see computational topics that have the same intellectual origins in physical proximity to one another. Finally, the text illustrates the "big ideas" that computation theory is built upon with applications of these ideas within "practical" domains in mathematics, computer science, computer engineering, and even further afield. Suitable for advanced undergraduate students and beginning graduates, this textbook augments the "classical" models that traditionally support courses on computation theory with novel models inspired by "real, modern" computational topics,such as crowd-sourced computing, mobile computing, robotic path planning, and volunteer computing. Arnold L. Rosenberg is Distinguished Univ. Professor Emeritus at University of Massachusetts, Amherst, USA. Lenwood S. Heath is Professor at Virgina Tech, Blacksburg, USA. .

Contents:

Preface

I: Introduction

1 Introducing Computation Theory

2 Introducing the Book

II: Pillar S: STATE

3 Pure State-Based Computational Models

4 The Myhill-Nerode Theorem: Implications and Applications

5 Online Turing Machines and the Implications of Online Computing

6 Pumping: Computational Pigeonholes in Finitary Systems

7 Mobility in Computing: An FA Navigates a Mesh

8 The Power of Cooperation: Teams of MFAs on a Mesh

III: Pillar E: ENCODING

9 Countability and Uncountability: The Precursors of ENCODING

10 Computability Theory

11 A Church-Turing Zoo of Computational Models

12 Pairing Functions as Encoding Mechanisms

IV: Pillar N: NONDETERMINISM

13 Nondeterminism as Unbounded Parallelism

14 Nondeterministic Finite Automata

15 Nondeterminism as Unbounded Search

16 Complexity Theory

V: Pillar P: PRESENTATION/SPECIFICATION

17 The Elements of Formal Language Theory

A A Chapter-Long Text on Discrete Mathematics

B Selected Exercises, by Chapter

List of ACRONYMS and SYMBOLS

References

Index.

Other Format:

Printed edition:

ISBN:

978-3-031-10055-0

9783031100550

Access Restriction:

Restricted for use by site license.