1 votes 1 votes Hi Guys, I think $S_{1}$ is not TRUE because input could be copied in other part of tape. So power of TM will not reduce. What is your opinion ? Theory of Computation made-easy-test-series theory-of-computation turing-machine + – Chhotu asked Nov 25, 2017 • edited Mar 3, 2019 by adeebafatima1 Chhotu 1.0k views answer comment Share Follow See all 17 Comments See all 17 17 Comments reply Show 14 previous comments srestha commented Nov 25, 2017 reply Follow Share @Shubhanshu @Manu Thakur, Turing Machine cannot write a portion of tape(this part is read only and regular language) But other portion of tape (can not be read only, and will be recursive ) So, the intersection of these two will be recursive Then TM can only recognize regular language - is not correct 0 votes 0 votes Hemant Parihar commented Nov 25, 2017 reply Follow Share Sorry, for the whole mess. I found this, where they consider both cases, 1. TM can't write on the input portion, but other portion it can. 2. TM can't write on the input tape. In both cases, they prove that it can only recognize the regular language. They give detail proof still trying to understand it. https://cs.stackexchange.com/questions/22082/single-tape-turing-machines-with-write-protected-input-recognize-only-regular-la 2 votes 2 votes Chhotu commented Nov 25, 2017 reply Follow Share Thank you @Hemant Parihar ji, Some other related questions are --> https://gateoverflow.in/26653/gate1991-17-a https://gateoverflow.in/75866/madeeasy-test-series 0 votes 0 votes Please log in or register to add a comment.
