# What is a generalized automaton that has ability to look up anything in memory from environment?

An automaton determines its next state from the current state and the next input symbol. A pushdown automaton adds a stack which you can push/pop/read from. But then there are probably a lot of intermediate things to a completely generic system where each transition is based on the current transition and any information from the environment. For example, a traditional function in an imperative language like JavaScript is essentially this sort of thing, where it goes to a function, then based on the lexical and global scopes, it figures out what input to pass to the next function (essentially). What is this sort of system? How to formalize this into an automaton sort of thing?

Is this just a register machine? If so, what is the best formalization of the mathematical model (in terms of research papers or books) which is freely available? Or better yet, what is the mathematical model listed explicitly here? If not, what is it?

Wondering if there is anything that models this sort of system using states and such. Wondering what the relation is to a FSM, and how to translate one to the other if possible, or at least relate them.

• A register machine is the equivalent of Turing Machines with the ability to "look up anything from its memory". Its significantly stronger than pushdown-automaton or FSMs Jun 20, 2021 at 20:27
• I would like to see something that somehow equates "instructions" of a RAM machine with the transitions of a FSM then, making it more formal and mathematical, etc. Jun 20, 2021 at 20:36

Now with memory type $$X$$ we can build an $$X$$-automaton. Such an automaton is basically a finite state automaton with its usual one-way input tape, equipped with an additional memory device of type $$X$$. Instructions of the automaton are roughly of the form $$(p,a,T,F,q)$$ That is short for:
In state $$p$$, reading $$a$$ from the input, and configuration $$C$$, we can move, provided $$C$$ satisfies the combination of tests $$T$$, the new state will be $$q$$, and the new configuration will be $$F(C)$$ obtained by applying the sequence $$F$$ of instructions.
With the usual initial and final states one can define computations (that should start with specific initial memory configurations) and the family of languages accepted by such $$X$$-automata.