Is a register machine built out of automata of some sort?

Question

I am looking at register machines like the Random Access Machine. Wikipedia says:

Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. Instructions are in the finite state machine in the manner of the Harvard architecture.

Does this mean the instructions are somehow encoded as a finite automaton? Or how exactly is a register machine implemented (theoretically and practically, at a high level). Where do automata fit into the picture?

I am wondering because I realize automata are pretty limited in what they can do, and once you need to "parse" something but have access to an entire database of information at each step of the parse, and then the result of parsing is a complicated object graph, you are no longer dealing with automata (as far as I can tell). Automata are basically recognizers returning a yes or no answer, with very little access to "data" to make their transition decisions. But I like the idea of "state machine", where it transitions around state to state.

So I'm wondering what a so-called "state machine" with access to a large database to figure out how to make each transition might be called, and if this is what a register machine could/would be.

My understanding is that a complex register machine is closer to something like x86, where you have instructions and data. But it seems that you might somehow be able to encode these instructions as a state machine somehow. Is this true? What am I missing from this picture? Is a register machine compiled down to automata of some sort, or otherwise built out of automata, or if not, how is it different from automata?

Answer 1

I can only react to this as seen from the perspective of a theoretical computer scientist.

A finite state machine/automaton is, as you know, usually represented by a finite directed graph. The vertices of the graph repesent the states of the automaton, the edges are the instructions: in state $p$, upon reading symbol $a$, move to state $q$. Next to this graph is the "machine interpretation". The machine has a control unit and an input tape. That control unit is represented by the finite graph.

From these finite state machines/automata we can build more complex automata by adding external memory. For instance the pushdown automaton. The external memory is a single stack. The edges/instructions of the finite state repesentation are now extended with tests and instructions of the external pushdown: test what is the topmost symbol $A$, pop $A$ and push a new sequence $\alpha$.

The register machine likewise is obtained by choosing another external memory type. That of registers. The machine has a finite, fixed, number of registers each holding a natural number. Each register can be tested for zero, incremented and decremented. The instructions of the register machine are added to the finite state control. So we get edges/instructions of the form: in state $p$ upon reading $a$, when register $i$ is nonempty, increment it by $1$ and move to state $q$. If we allow the register machine to read $\varepsilon$, that is compute without reading input, these machines are Turing complete (even with two registers).