Chapter 11: Computability l;;! 333
11.4.2 A TURING MODEL FOR COMPUTATION
As in the model introduced in Chapter 9, Q, qo and r denote the set of states.
the initial state, and the set of tape symbols, respectively. The blank symbol b
is in r. The only difference is in the transition function. In the present model
the transition function represents only one of the following three basic
operations:
(i) Writing a new symbol in the cell scanned
(ii) Moving to the left cell
(iii) Moving to the right cell
Each operation is followed by a change of state. Suppose the Turing machine
M is in state q and scans ai' If ai is written and M enters q', then this basic
operation is represemed by the quadruple qaiad. Similarly. the other two
operations are represented by the quadruples qaiLq' and qaiRq'. Thus the
transition function can be specified by a set P of quadruples. As in Chapter 9.
we can define instantaneous descriptions, i.e. IDs.
Each quadruple induces a change of IDs. For example, qa;ajq' induces
P. '
, [3
CI.qail-' I aq ai
The quadruple qaiLq' induces
and qaiRq' induces
When we require M to perform some computation, we 'feed' the input by
initial tape expression denoted by X. So qaX is the initial ID for the given
input. For computing with the given input X. the Turing machine processes
X using appropriate quadruples in P. As a result. we have qoX =ID i r- ID 2
r- .... When an ID. say IDil' is reached. which cannot be changed using any
quadruple in P, M halts. In this case, ID" is called a terminal ill. Actually,
aqj a[3 is a terminal ID if there is no quadruple starting with qi{l. The terminal
ID is called the result of X and denoted by Res(X). The computed value
cOlTesponding to input X can be obtained by deleting the state appeming in it
as also some more symbols from Res(X).
11.4.3 TURING-COMPUTABLE FUNCTIONS
Before developing the concept of Turing-computable functions. let us recall
Example 9.6. The TM developed in Example 9.6 concatenates two strings a
aej [3. Initially, a and [3 appear on the input tape separated by a blank b.
Finally, the concatenated string a[3 appears on the input tape. The same
method can be adopted with slight modifications for computing I(x] , ..., x,,')'
Suppose we want to construct a TM which can compute I(xl' ... , XII,) over
11.4.2 A TURING MODEL FOR COMPUTATION
As in the model introduced in Chapter 9, Q, qo and r denote the set of states.
the initial state, and the set of tape symbols, respectively. The blank symbol b
is in r. The only difference is in the transition function. In the present model
the transition function represents only one of the following three basic
operations:
(i) Writing a new symbol in the cell scanned
(ii) Moving to the left cell
(iii) Moving to the right cell
Each operation is followed by a change of state. Suppose the Turing machine
M is in state q and scans ai' If ai is written and M enters q', then this basic
operation is represemed by the quadruple qaiad. Similarly. the other two
operations are represented by the quadruples qaiLq' and qaiRq'. Thus the
transition function can be specified by a set P of quadruples. As in Chapter 9.
we can define instantaneous descriptions, i.e. IDs.
Each quadruple induces a change of IDs. For example, qa;ajq' induces
P. '
, [3
CI.qail-' I aq ai
The quadruple qaiLq' induces
and qaiRq' induces
When we require M to perform some computation, we 'feed' the input by
initial tape expression denoted by X. So qaX is the initial ID for the given
input. For computing with the given input X. the Turing machine processes
X using appropriate quadruples in P. As a result. we have qoX =ID i r- ID 2
r- .... When an ID. say IDil' is reached. which cannot be changed using any
quadruple in P, M halts. In this case, ID" is called a terminal ill. Actually,
aqj a[3 is a terminal ID if there is no quadruple starting with qi{l. The terminal
ID is called the result of X and denoted by Res(X). The computed value
cOlTesponding to input X can be obtained by deleting the state appeming in it
as also some more symbols from Res(X).
11.4.3 TURING-COMPUTABLE FUNCTIONS
Before developing the concept of Turing-computable functions. let us recall
Example 9.6. The TM developed in Example 9.6 concatenates two strings a
aej [3. Initially, a and [3 appear on the input tape separated by a blank b.
Finally, the concatenated string a[3 appears on the input tape. The same
method can be adopted with slight modifications for computing I(x] , ..., x,,')'
Suppose we want to construct a TM which can compute I(xl' ... , XII,) over