Register

CMI2011-A-09

1,715 views

1 Answer

3 3 votes

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.

Voting & Accepting an answer helps improve the community
← Previous · CMI2011-A-08Next → · CMI2011-A-10
← Previous in category · CMI2011-A-01Next in category → · CMI2011-B-04a
Position:
Show:

Related questions

1 1 vote
2 2 answers
1.4k
1.4k views
go_editor asked May 19, 2016
1,422 views
CMI2011-A-01
Let L $\subseteq \{0, 1\}^∗$ be a language accepted by a finite automaton. Let $F$ be some subset of $\{0, 1\}^∗$, containing 2011 strings. Which of the fol...
1 1 vote
2 2 answers
1.0k
1.0k views
go_editor asked May 27, 2016
1,024 views
CMI2011-B-04b
Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the l...
1 1 vote
2 2 answers
803
803 views
go_editor asked May 19, 2016
803 views
CMI2011-B-04a
Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the lan...
5 5 votes
1 1 answer
839
839 views
go_editor asked May 19, 2016
839 views
CMI2011-A-10
Consider the following functions $f$ and $g$:f(){ x = x+1; x = y*y; x = x-y; }g(){ y = y+1; y = x*x; y = y-x; }Suppose we start with initial values of $1$ for $x$ and $2$...