3 ms·

That means a (properly) relational DBMS can be completely locked down because the relational model is not Turing complete.

by ben509 7y ago

ben509 7y ago
The goal here is to find a criteria under which you can require that manufacturers open up general purpose systems. And the proposal is that a system that is Turing complete is also general purpose. The relational model is hugely expressive, and yet it is not Turing complete. So you have something that is plainly general purpose, but would be exempt from such a law. That you can modify the relational model to make it Turing complete is irrelevant, it's already hugely expressive. And that you'd typically run it on a machine that is Turing complete doesn't save you. If a manufacturer wanted to bypass that restriction, they'd design a system that is entirely dedicated to it.
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 ago
  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.
DenisM 7y ago
CTEs make SQL Turing-complete IIRC. [1] https://docs.microsoft.com/en-us/sql/t-sql/queries/with-common-table-expression-transact-sql?view=sql-server-ver15 https://docs.microsoft.com/en-us/sql/t-sql/queries/with-comm...
- ben509 7y ago
  Procedural SQL definitely does, but see my response to myself.

That means a (properly) relational DBMS can be completely locked down because the relational model is not Turing complete.

by ben509 7y ago

That means a (properly) relational DBMS can be completely locked down because the relational model is not Turing complete.

ben509 7y ago

The goal here is to find a criteria under which you can require that manufacturers open up general purpose systems. And the proposal is that a system that is Turing complete is also general purpose. The relational model is hugely expressive, and yet it is not Turing complete. So you have something that is plainly general purpose, but would be exempt from such a law. That you can modify the relational model to make it Turing complete is irrelevant, it's already hugely expressive. And that you'd typically run it on a machine that is Turing complete doesn't save you. If a manufacturer wanted to bypass that restriction, they'd design a system that is entirely dedicated to it.

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 ago
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.

DenisM 7y ago

CTEs make SQL Turing-complete IIRC. [1] https://docs.microsoft.com/en-us/sql/t-sql/queries/with-common-table-expression-transact-sql?view=sql-server-ver15 https://docs.microsoft.com/en-us/sql/t-sql/queries/with-comm...

ben509 7y ago
Procedural SQL definitely does, but see my response to myself.