O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required