You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your laptop?
(a) Turing machine (b) Linear bounded automaton (c) Pushdown automaton (d) Finite state automaton
First of all I don't mind saying that I could not interpret well enough. I understand it conveys that the memory is limited but how much that affect when it is connected to any external device is blur to me.Help appreciated.
N.B- This is not a homework question.Its from a pg admission exam.
Source- http://www.cmi.ac.in/admissions/sample-qp/pgcs2011.pdf
They just put the bit about external devices in so that you would be sure that you couldn't, for example, plug in a drive to make the storage bigger.
A Turing machine has an unlimited tape, so your finite-memory computer can't satisfy that. Similarly a pushdown automaton has a potentially-unlimited stack.
However, a computer is fully programmable, while a finite state machine is not. So, while strictly your computer has a finite number of states and well-defined transitions between them (since its memory and CPU together have only finitely many possible states), I would say it is more like a linear bounded automaton.