This theory makes use of Turing machines to demonstrate the mathematical limits of computation. Indeed, any computation beyond the power of Turing machines is also beyond the computer power. The Turing machine represents a relatively simple language -defining model. Consider Turing machines as computers of functions over nonnegative integers and demonstrates the existence of functions whose computation cannot be specified by any procedure.

Chapter Contents:

• 9.1 Functions computed by Turing machines
• 9.2 Mathematical theory of computability: an introduction

Inspec keywords: Turing machines; computability

Other keywords: computer power; nonnegative integers; mathematical limits; turing machines; computability; computation

Subjects: Automata theory; Formal logic