332 .\;l Theory of Computer Science
So far we have dealt with recursive and partial recursive functions over
N. We can define partial recursive functions over L using the primitive
recursive predicates and the minimization process. As the process is similar,
we \vi11 discuss it here.
The concept of recursion occurs in some programming languages when a
procedure has a call to the same procedure for a different parameter. Such a
procedure is called a recursive procedure. Certain programming languages like
C, C++ allow recursive procedures.
11.4 PARTIAL RECURSIVE FUNCTIONS AND TURING
MACHINES
In this section we prove that partial recursive functions introduced in the earlier
sections are Turing-computable.
11.4.1 COMPUTABILITY
In mid 1930s. mathematicians and logicians were trying to rigorously define
computability and algOlithms. In 1934 Kurt GOdel pointed out that primitive
recursive functions can be computed by a finite procedure (i.e. an algorithm).
He also hypothesized that any fL1nction computable by a finite procedure can
be specified by a recursive function. Around 1936, Tming and Church
independently designed a 'computing machine' (later termed Turing machine)
\vhich can carry out a finite procedure.
For formalizing computability, Turing assumed that. while computing, a
person wlites symbols on a one-dimensional paper (instead of a twodimensional paper as is usually done) which can be viewed as a tape divided
into cells. He scans the cells one at a time and usually peliorms one of the three
simple operations. namely (i) \vriting a new symbol in the cell he is scanning,
(ii) moving to the cell left of the present cell, and (iii) moving to the cell right
of the present cell. These observations led Turing to propose a computing
machine. The Turing machine model we have introduced in Chapter 9 is based
on these three simple operations but with slight variations. In order to introduce
computability, \ve consider the Turing machine model due to Post. In the
present model the transition function is represented by a set of quadruples (i.e.
4-tuples), whereas the transition function of the model we have introduced in
Chapter 9 can be represented by a set of quintuples (5-tuples). For example,
6(qj. a) = (qj, a, {3) is represented by the quintuple qjaa{3CJj. Using the model
specifying the transition function in terms of quadruples. we define Turingcomputable functions and prove that partially recursive functions are Turingcomputable.
So far we have dealt with recursive and partial recursive functions over
N. We can define partial recursive functions over L using the primitive
recursive predicates and the minimization process. As the process is similar,
we \vi11 discuss it here.
The concept of recursion occurs in some programming languages when a
procedure has a call to the same procedure for a different parameter. Such a
procedure is called a recursive procedure. Certain programming languages like
C, C++ allow recursive procedures.
11.4 PARTIAL RECURSIVE FUNCTIONS AND TURING
MACHINES
In this section we prove that partial recursive functions introduced in the earlier
sections are Turing-computable.
11.4.1 COMPUTABILITY
In mid 1930s. mathematicians and logicians were trying to rigorously define
computability and algOlithms. In 1934 Kurt GOdel pointed out that primitive
recursive functions can be computed by a finite procedure (i.e. an algorithm).
He also hypothesized that any fL1nction computable by a finite procedure can
be specified by a recursive function. Around 1936, Tming and Church
independently designed a 'computing machine' (later termed Turing machine)
\vhich can carry out a finite procedure.
For formalizing computability, Turing assumed that. while computing, a
person wlites symbols on a one-dimensional paper (instead of a twodimensional paper as is usually done) which can be viewed as a tape divided
into cells. He scans the cells one at a time and usually peliorms one of the three
simple operations. namely (i) \vriting a new symbol in the cell he is scanning,
(ii) moving to the cell left of the present cell, and (iii) moving to the cell right
of the present cell. These observations led Turing to propose a computing
machine. The Turing machine model we have introduced in Chapter 9 is based
on these three simple operations but with slight variations. In order to introduce
computability, \ve consider the Turing machine model due to Post. In the
present model the transition function is represented by a set of quadruples (i.e.
4-tuples), whereas the transition function of the model we have introduced in
Chapter 9 can be represented by a set of quintuples (5-tuples). For example,
6(qj. a) = (qj, a, {3) is represented by the quintuple qjaa{3CJj. Using the model
specifying the transition function in terms of quadruples. we define Turingcomputable functions and prove that partially recursive functions are Turingcomputable.