4 ms·

Practitioners are usually concerned about what is true in practice. Weaker computational models have found great success in databases and parallel programming (

Practitioners are usually concerned about what is true in practice. Weaker computational models have found great success in databases and parallel programming (e.g. Googles MapReduce) because they are easier, in practice, to reason about and optimise.

pron 9y ago
> Weaker computational models have found great success in databases and parallel programming (e.g. Googles MapReduce) because they are easier, in practice, to reason about and optimise. Most SQL variants [1] and map-reduce [2] are Turing complete. They are easier to optimize in practice because they tend to be small and simple (compilers often make similar optimizations for similarly-sized general purpose programs) and because they express the parts that are important to optimize for that particular problem (data-dependence and parallelism) in a direct way -- not because of the computational model. You could argue that because SQL is cumbersome for general-purpose programming it helps ensure programs are small and simple, but most people would rather not write their application in SQL, and if they did, it would no longer be small and simple. [1]: https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete https://stackoverflow.com/questions/900055/is-sql-or-even-ts... [2]: https://www.quora.com/Theoretically-can-any-algorithm-be-implemented-in-MapReduce-framework https://www.quora.com/Theoretically-can-any-algorithm-be-imp...
- willtim 9y ago
  SQL Turing completeness is generally regarded as a (relatively recent) mistake. MapReduce is only regarded as Turing complete as it is typically programmed using Turing complete languages. In both cases, the validity of many optimisations would be destroyed by any non-terminating behaviour. You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Perhaps a better example is the humble Regex. If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation.
  - pron 9y ago
    > You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Termination and exponential (or super-exponential) running times are about equally bad. Avoiding either is done on a case-by-case basis. Restricting the language can save you from one and not the other. > If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation. I'm not an expert on regex by any means, but I believe this optimization is exponential (a DFA can be exponential in the size of the regex), and so infeasible in practice. Regardless, as I said, regex is about as far down as we can take computation, and regexps make for a very poor generally useful computational construct.

pron 9y ago

> Weaker computational models have found great success in databases and parallel programming (e.g. Googles MapReduce) because they are easier, in practice, to reason about and optimise. Most SQL variants [1] and map-reduce [2] are Turing complete. They are easier to optimize in practice because they tend to be small and simple (compilers often make similar optimizations for similarly-sized general purpose programs) and because they express the parts that are important to optimize for that particular problem (data-dependence and parallelism) in a direct way -- not because of the computational model. You could argue that because SQL is cumbersome for general-purpose programming it helps ensure programs are small and simple, but most people would rather not write their application in SQL, and if they did, it would no longer be small and simple. [1]: https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete https://stackoverflow.com/questions/900055/is-sql-or-even-ts... [2]: https://www.quora.com/Theoretically-can-any-algorithm-be-implemented-in-MapReduce-framework https://www.quora.com/Theoretically-can-any-algorithm-be-imp...

willtim 9y ago
SQL Turing completeness is generally regarded as a (relatively recent) mistake. MapReduce is only regarded as Turing complete as it is typically programmed using Turing complete languages. In both cases, the validity of many optimisations would be destroyed by any non-terminating behaviour. You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Perhaps a better example is the humble Regex. If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation.
- pron 9y ago
  > You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Termination and exponential (or super-exponential) running times are about equally bad. Avoiding either is done on a case-by-case basis. Restricting the language can save you from one and not the other. > If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation. I'm not an expert on regex by any means, but I believe this optimization is exponential (a DFA can be exponential in the size of the regex), and so infeasible in practice. Regardless, as I said, regex is about as far down as we can take computation, and regexps make for a very poor generally useful computational construct.