A finite state machine can control the head of a Turing machine (as, that is what controls the head of a Turing machine). A transformer could be trained to imp

A finite state machine can control the head of a Turing machine (as, that is what controls the head of a Turing machine). A transformer could be trained to implement a particular finite state machine (using a fixed length context window). Of course, so could a fully connected 1-hidden-layer feed-forward neural network. Though, a lookup table would probably be more practical than either of those. I'm not saying much here, just that "technically, a transformer equipped with interaction with another system, can be Turing complete (though not necessarily in a way that matters)." . Giving a finite state machine the ability to read and write finite amounts of information to memory addresses (where each address can only store a finite amount of info), only goes beyond being a (perhaps much larger) finite state machine, if there are infinitely many memory locations that can be used, and so these locations can't be limited to ones that have an address which can be specified entirely in terms of a state of the finite state machine. the following is a tangent: Sometimes I wonder about, "If we wanted to design a computer that used silicon chips and other such electrical components, but was modular in a way that would make it technically Turing complete as long as we connected (and provided adequate power to) additional modules whenever it tried to use the next one it is missing, what would be a good way to design that?". A single tape of symbols, or even several tapes, where it can only move one position at a time (per tape), seems probably inefficient (though perhaps not in any asymptotic sense). But, if one can only jump to positions labeled by addresses of a bounded length, that's no good. Therefore, I think that maybe a good solution would be to use relative addresses, where the offsets have a maximum size of 2^32 or 2^16 or something. I think that, in order to prevent computation at later memory addresses from being slower, having to send the information back and forth between the module where it is stored and the information describing the FSM/program, it might be good to have either all the modules, or some fraction of them, contain copies of the hardware for running the computation steps, not just forwarding and implementing messages to read/write. Though, in that case, it does seem a bit of a waste to not use parallelism. Alternatively, I suppose having a literally-moving head, which stores the FSM, and moves between the different memory modules, might make sense?