It wouldn't be turing complete if you simply load the application into ROM and restrict the CPU from executing pages in RAM. You can implement the entire relat

It wouldn't be turing complete if you simply load the application into ROM and restrict the CPU from executing pages in RAM. You can implement the entire relational model with about 8 operators and graph transformations, mostly distribution. You can add math functions as virtual tables, e.g. join against the times table to do multiplciation. I wrote a paper on how this works, and while it was about ten years ago, I'm pretty sure you could do the algebraic transformations needed with just a stack, so I think you could do it with a finite state automata. But see my response to myself.