Question 3: Turing Machines and Complexity Consider the following deterministic Turing machine M on alphabet 2 = {a. b.-

[answerhappygod]

Question 3 Turing Machines And Complexity Consider The Following Deterministic Turing Machine M On Alphabet 2 A B 1 (38.59 KiB) Viewed 35 times

Question 3: Turing Machines and Complexity Consider the following deterministic Turing machine M on alphabet 2 = {a. b.-). The tape initially contains a nonempty block of a's and b's on an otherwise blank tape with the head on the leftmost character. The transition function is given by the following diagram: Return True Read a,b, L Read Right Read 8 Left Read a,b Left 7 Write- Write- 2 6 Right Read a b Right 3 (a) Trace the behaviour of the machine M on the word aa. (b) Recall the notation X for xo + x₂ + + Xp. The processing time for a block of length n>0 is as follows. Read Left 5 Read M R Read a b F Return False [7 marks] • In the case where n=2p+2 (p>0) the number of steps is (Σ(8k+12))+2. • In the case where n = 2p+1 (p > 0) the number of steps is (Σ(8k+8))-1. Show that the complexity of M is in O(n²). [8 marks]