I heard that it's possible to model a bounded-memory RAM as a Finite State Machine.
I'm curious about the method of how we would do that.
How would you model a bounded-memory RAM as a Finite State Machine?
Thanks in advance
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Consider a RAM machine with $n$ memory cells, and suppose each cell contains a bit. In addition, you have a control with $k$ states.
A configuration of this machine consists of the state of the control, and the contents of the memory. Thus, there are $k\cdot 2^n$ configurations.
You can view each configuration as a state of a FSM, and the transitions between configurations are determined by the state of the control and the effect it has on the memory.