Introduction to Automata Theory, Formal Languages and Computation

11

Recursive Function

Introduction

In the ‘Turing machine as integer function’ section of the chapter ‘Extension of the Turing Machine’, different integer functions such as addition, subtraction, multiplication, remainder finding, square, etc. are constructed using the Turing machine. These are the basic functions. By combining these basic functions, complex functions are constructed. As the basic functions are computable, the complex functions are also computable.

Like the theory of the Turing machines, the recursive function theory is a way to make formal and precise the intuitive, informal, and imprecise notion of an effective method. Like the theory of the Turing machines, the recursive function theory also obeys the converse of the Church’s ...