CMI2011-A-09

Question

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

Answer 1

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 or infinite. It make your computer as finite-memory machine. 

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.

Comments

@Arjun sir, please verify this. 

---

quoting from wiki on Linear Bounded Automata;

"instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers"

---

@rude if memory is finite, then even if programmed we end up with finite states rt? Also, if we say it is not a PDA it can never be a LBA rt?

---

@Arjun Let's have a simple argument, It can not be FA and PDA  because it read and write to the same memory. Now it can not be a turing machine because it is not having infinite memory.

It can be LBA, it allows read and writes at the same memory location, as well as the finite amount of memory. The only difference between LBA and TM is the memory constraints.