turing machine

Question

If we limit the size of tape in turing machine, what would be the resultant machine?

Answer 1

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.

Comments

@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.

---

ooh..alright.i have understood :-)

and how can we limit turing machins as LBA??

---

Read above answer. ;-)

Answer 2

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??