0 votes 0 votes If we limit the size of tape in turing machine, what would be the resultant machine? Theory of Computation theory-of-computation turing-machine + – vaishali jhalani asked Dec 14, 2016 vaishali jhalani 565 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Depends upon how we restrict the tape. If we restrict a tape being used like a stack it is only PDA but if we restrict tape used as a function of input it is LBA. Aghori answered Dec 14, 2016 • reshown Dec 14, 2016 by Aghori Aghori comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Aghori commented Dec 15, 2016 reply Follow Share @akriti In simple terms, every Regular language (of FM), CFL (of PDA), CSL (of LBA) is proper subset of recursively enumerable language which TM deals. It means you can always limit TM to simulate FM,PDA & LBDA. You can also say all computational machines are limited version of TM. 0 votes 0 votes Akriti sood commented Dec 15, 2016 reply Follow Share ooh..alright.i have understood :-) and how can we limit turing machins as LBA?? 0 votes 0 votes Aghori commented Dec 15, 2016 reply Follow Share Read above answer. ;-) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes If we limit the tape to the length multiple of input length then it is LBA. If we make the length finite then it is FA. I think we can limit it like that. I don't get how we can restrict the tape to be used as stack?? Lucky sunda answered Jan 20, 2017 Lucky sunda comment Share Follow See all 0 reply Please log in or register to add a comment.