Discrete Mathematics and Combinatorics

Chapter 12

Turing Machines and Computable Functions

Learning Objectives

On completing this chapter, you should be able to:

• define initial functions that are the buliding blocks of computable functions

• present primitive recursive definitions for commonly used functions

• state the definition of a recursive function

• compute the values of the Ackerman’s function for various values of its variables

• state the definition of a computable function

• prove that a given function is computable by constructing a Turing machine, which computes the given function

• give the sketch of the proof of the theorem, which asserts that every recursive function is computable

• recognize that the class of recursive and computable functions are identical

12.1 RECURSIVE AND ...