Question

02. Design Turing machine to compute the following function for x positive integers represented in unary. f (x) x mod 4.

Answer 1

Given, t(n)= χ mod 4 The input to our tape u be u(x) and -he output u ill be U(X mod 4 The 9dea s to mark all the 1.'ろ tote Yǐght using our stares to remember as coe scan how many AA ue have Seen mod 4 Then, we' remove the marks from that manq is and Scan back to the left ove the renoining marked 5 Then e o delete al the marked ones and halt with χ mod 4 on the tape Scanned with CamScanner

he turinq machine can be defed as -follouo ohere Start State n stare tohere Ts β defined as -jol loos : δ (%,i)-(4,,3. R), s blank space on tope Simbol * Mark a '1' and move lo the State 1 mod A to he state mod 4 δ (4'') = C φ3,Ý, R) , Mark a 11' and move the Stare 3 mod 4 S(43) (L R), Mark a '1' and move to he state o mod 4, 9 unt the end e beati s Scanned with CamScanner

do, □) = C do ,-ti, L) → Remember uhich ever State we ended.n, 8 () (4o, 4,L) and unmark -that mang 13 Here, hle le our answer) back to beginnin marked ', VA, A, L)^ untft we -find an unmarked 1' δ (4,4,n) ,0, R) and then halt. Scanned with CamScanner