Chapter 9
AUTOMATA
9.1 INTRODUCTION
The goal of this chapter is to understand the foundations of computation. We shall ask some very basic questions, such as:
- What does it mean for a function to be computable?
- Are there any noncomputable functions?
- How does computational power depend on programming constructs?
These questions may appear simple, but they are not.
In the quest for answers to these questions, we will encounter, along the way, some fundamental and pervasive concepts: state, transition, nondeterminism, reduction, and undecidability, to name a few. Some of the most important achievements in theoretical computer science have been the crystallization of these concepts. They have shown a remarkable persistence, even as technology changes ...
Get Discrete Mathematics now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
