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