0 votes 0 votes Cant we infer that their complexity remains same Theory of Computation turing-machine + – Pawan Kumar 2 asked Jan 30, 2018 Pawan Kumar 2 292 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Arjun commented Jan 30, 2018 reply Follow Share Please read the whole sentence -- it says "what can be done by the machine" - not "how". So both machines accept the same set of languages but can differ in their running times. 1 votes 1 votes Pawan Kumar 2 commented Jan 30, 2018 reply Follow Share Arjun Sir JI .. Thank you very much 0 votes 0 votes rajatmyname commented Jan 30, 2018 reply Follow Share Sir, how you conclude that the complexity of single tape turing machine will become (T(n))**2? 1 votes 1 votes register_user_19 commented Dec 26, 2018 reply Follow Share https://gateoverflow.in/113193/ace-test-series i think most of the test series question is already asked in the last year, so before posting, just search for it. 0 votes 0 votes Please log in or register to add a comment.