- Algorithm Written In Plain English That Describes The Work Of A Turing Machine N Is On Input String W While There Are Un 1 (36.71 KiB) Viewed 36 times
- Algorithm Written In Plain English That Describes The Work Of A Turing Machine N Is On Input String W While There Are Un 2 (105.47 KiB) Viewed 36 times
Algorithm written in plain English that describes the work of a Turing Machine M is On input string w while there are unmarked Os, do Mark the left most 0 Scan right till the leftmost unmarked 1; if there is no such 1 then crash Mark the leftmost 1 done Check to see that there are no unmarked 1s; if there are then crash accept (a) Formal Definition of the Turing machine M is M = (Q, E, I, 6, 90, 9acc, grej) where • Q = {90, 91, 92, 93, 9acc, grej} Σ= {0, 1}, and I = {0, 1, A, B, L} • 8 is given as follows 8(qo, 0) (q1, A, R) 8(91,0) = (1, 0, R) 8(q₁, 1) = (92, B, L) 8(92,0)= (92,0, L) 8(93, B) = (93, B, R) 8(90, B) = (93, B, R) 8(q₁, B) = (q₁, B, R) 8(92, B) = (92, B, L) = 8(92, A) (90, A, R) 8(93, L) = (qacc, U, R) In all other cases, 8(q, X) = (grej, L, R). So for example, 8(qo, 1) = (grej, L, R).