Turing Machine as function computer
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Webpage: www.krchowdhary.com
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Monday 10th April, 2017

kr chowdhary

TOC

1/ 1

Computing with TM

Turing machine can compute functions, like y = f (x). Initially a
value corresponding to x is put on the tape, and Turing machine is
run. after having performed the computations, the result f (x) will
replace the original value, and head returns to begin.
The input is usually represented in unary format. For 0 is represented
1, the 1 is represented as 11 and n is represented as 1n+1 .
To add two numbers m and n represented as 1m+1 and 1n+1 . Their
sum m + n is 1m+n−1 .
The set of arguments for the function f (x1 , x2 , . . . , fn ) is put on the
tape as a string of 1s and 0s, having value B1x1 B1x2 B . . . i xn .

kr chowdhary

TOC

2/ 1

Function Computing with TM

To find out the sum of m + n, the arguments are stored on tape in
the begin as B1m+1 B1n+1 B, with ID as q0 B1m+1 B1n+1 B. The head
will scan the tape, replacing the center B separator with 1, finally
two 1s at the end are replaced by 0s, to obtain ID as qj B1m+n−1 .
1|1, R
q0

B | B, R q1

1|1, R

q2

1|1, R
B|1, R

1|1, R

q3

q4

B|B, L

q5
1|B, L

1|1, L

q9

B|B, R

q8

1|1, L

q7

1|B, L
q6

Figure 1: Turing machine adding m and n.

kr chowdhary

TOC

3/ 1

Primitive recursion functions: Successor function
All computations in TM can be done using primitive recursive (PR)
functions. The zero (Z ) and successor (S) functions are PR and
composition of PR with PR are PR, and nothing else are PR.
For example, to find 3 + 2, we can do this by succ(succ(3)). This is
nothing but S ◦ S(3), which is composition of the function S with
itself. If the n is an integer, represented in unary as 1n+1 , then its
successor is 1n+1 , and can be computed using TM as follows:
1|1, L

1|1, R
S(n)=

q0

B | B, R q1

1|1, R

q2

B|1, L

q3

B|B, R

q4

Figure 2: Turing machine computing the successor function.

kr chowdhary

TOC

4/ 1

Successor function for binary number
Sample Rules:

000101B

If read 1, write 0, Go Right,
repeat.

000001B
0 0 0 0 1 1 B ;Rewinds and
HALTS; the result is 48 in
reverse order.

If read 0, write 1, Rewind and
halt

So the successor’s output on
111101 was 000011 which is
the reverse binary
representation of 48.

If read B, write 1, rewind and
halt
Let’s see how they are carried
out on a piece of paper that
contains the binary
representation of 47 in reverse
order:bold number represents
position of head.

1|1, L
0|0, L

1|0, R
q0

B|B, R

q1

1|0, R

q2

B|1, L
0|1, R

q3 B|B, S

111101B
Figure 3: Successor TM for binary
number.

011101B
001101B
kr chowdhary

TOC

5/ 1

q4

Primitive recursive function: Zero (Z)

The Zero function is PR, and its effect is to make tape contents
equal to zero.
Thus, if contents of tape is 1n or it is 1m , after running Zero (Z)
function, the result on tape is 1, which stands for zero. The
following is TM for zero function.
B|B, L

1|B, R
Z(n)=

q0

B | B, R q1

1|1, R

q2

B|B, L

q3

1|1, L

q4

Figure 4: Turing machine computing the zero.

kr chowdhary

TOC

6/ 1

Primitive recursive function: Pred (n)
The predecessor function (pred) is a partial recursive function. Its
effect is to make tape contents reduced by 1.
Thus, if contents of tape is 1n+1 , after running pred function, the
result on tape is 1n . However, if it is zero, pred(1) = 1 (zero),
because predecessor of 0 is zero only, since we are dealing with
positive integers.
1|1, R
pred(n)=

q0

1|1, R

B | B, R q1

q2

1|1, R

q3

B|B, L

q4

B|B, L
1|B, L
q5

1|1, L

Figure 5: Turing machine computing the pred(n) function.

kr chowdhary

TOC

7/ 1

Concatination of functions.
To build complex TMs or to compute the complex functions, these
primitive recursive functions are called as library function, are joined
in sequential order. For example, to make tape zero (initialize), then
add 2 into the present value, the functions, Z, S, S are called in
sequence.
When the functions are concatinated like this, the final
(accepting/halting) state of the previous function becomes the start
of state of the next function, as shown in the figure below.

q0

Z

f1

1

s2

S
2

f2

S

s3

3

f3

Figure 6: using more than one PR functions.

kr chowdhary

TOC

8/ 1

Visualization (Simulation) of TM.
Considering calling the successor function. Let the tape content is
111, we can show the computation as shown in figure 7.
b
b

b

b
b

b

b
b

b
b

b

b
b
b

b
b

b

b

b

b

Time

b
b

b

b

b

b

b

b

b

b

b

b

b
b

b
b

state
change
seq. q0 − q6

b

b
b

b

b
b

b
b

b

b

b

b

b

0
1
2
2
3
3
4
5
5
6

b

b
b

b
b
b

Dots are postions holding 1s.
Squares are indicator of head positions w.r.t time

Figure 7: Simulation (visualization) of TM.
kr chowdhary

TOC

9/ 1

