Question 5 in the Final Exam on February 21st, 2022

Question 5 in the Final Exam on February 21st, 2022

by AHMAD SADIN -
Number of replies: 1

Hello Professor,

In part (a), can we argue that since the Turing Machine accepts the input in precisely 5 steps, it operates in polynomial time? Given that languages accepted in polynomial time by a Turing Machine are decidable, can we then conclude that Language 1 is decidable?



In reply to AHMAD SADIN

Re: Question 5 in the Final Exam on February 21st, 2022

by Giorgio Satta -

Dear Ahmad, the problem associated with L1 is to detect whether an input TM M recognises some string in exactly 5 steps. This does not mean that M operates in polynomial time on all of the strings in Sigma*.

I hope this answers to your question.