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

Question

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.

Answer 1

The theory you seem to be looking for is called AFA or "abstract family of acceptors". You can read an early version of it on wikipedia, but its notions are hard to parse, without examples and such.

For AFA theory we first define an abstract type of memory. This is very similar to abstract data type now common in data structures. Such a memory type first defines the domain of the memory, its storage configurations. For pushdown automata that is a stack (formalized as a string), for a register machine that is a sequence of natural numbers, for a TM that is a (working) tape.

Then the memory type needs tests and operations. Tests are Boolean functions that are applied to the memory. For a pushdown we can check emptyness or verify the topmost symbol. Operations are applied to the memory. For the PDA the operations are of obviously pop and push. We have to be careful, the operations can be partial.

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.