Consider the following Turing machine M with input alphabet {1}: 90 A/#R 91 A/1R 1/1 R 92 A/1R 1/1...

Transcribed Image Text:

Consider the following Turing machine M with input alphabet {1}: 90 A/#R 91 A/1R 1/1 R 92 A/1R 1/1 R 93 ha A/1R 1/1 R #/AS 94 1/AR A/AL 95 A/AL 1/1L (i) [2 marks] Assuming that each natural number n 20 is represented by the string 1", what function fM: N N does M compute? (ii) [5 marks] Give the function TM, the time complexity of M. (iii) [3 marks] Give the function SM, the space complexity of M.

Answer rating: 100% (QA)

SOLUTION i The Turing machine M appears to be a machine that performs some operations on the input string of 1s Let s analyze the transitions to determine its function A R This transition moves to sta View the full answer