3 ms·

> Who decides what qualifies as a general purpose Alan Turing and Alanzo Church. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikiped

by pdkl95 7y ago

> Who decides what qualifies as a general purpose Alan Turing and Alanzo Church. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness However, my use of the term is an explicit (my previous [2]) reference to these important talks by Cory Doctorow about the War on General Purpose Computing, which I strongly recommend watching/reading: https://boingboing.net/2012/01/10/lockdown.html https://boingboing.net/2012/01/10/lockdown.html https://boingboing.net/2012/08/23/civilwar.html https://boingboing.net/2012/08/23/civilwar.html

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.
ben509 7y ago
And by that standard, the avionics controller for a missile is general purpose.
sjwright 7y ago
I am aware of the origins of the term. The term certainly had relevance 30–90 years ago. What I reject is that the term has any meaning when attempting to form a distinction between an iPad and a MacBook.

by pdkl95 7y ago

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.

ben509 7y ago

And by that standard, the avionics controller for a missile is general purpose.

sjwright 7y ago

I am aware of the origins of the term. The term certainly had relevance 30–90 years ago. What I reject is that the term has any meaning when attempting to form a distinction between an iPad and a MacBook.