3 ms·
While the DBMS itself isn't Turing complete, you probably need a Turing equivalent machine to implement the DBMS. Turing machines can implement less complex ty
by pdkl95 7y ago
While the DBMS itself isn't Turing complete, you probably need a Turing equivalent machine to implement the DBMS. Turing machines can implement less complex types of automation, but the underlying machine is still Turing complete.
I wonder how difficult it would be to make a purely electromechanical decision table. ( https://en.wikipedia.org/wiki/Decision_table https://en.wikipedia.org/wiki/Decision_table )
- deleted 7y ago[deleted]
- ben509 7y agoIt 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.