Discrete Mathematics

----------------

'

Chapter9

----------------

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 ...