Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization?

Why is this case? What is the thought process and what are some examples in practice? What are some good resources on the topic?

  • $\begingroup$ Turing-completeness is a characteristic of a computational model, not a language. Do you mean Turing-recognizable or decidable perhaps? $\endgroup$ – dkaeae Jun 18 '19 at 14:54
  • $\begingroup$ Unless OP means programming language, rather than formal language. $\endgroup$ – jmite Jun 18 '19 at 14:59

The main advantage of having a Programming Language that is not Turing Complete is that your language can be strongly normalizing, that is, you can ensure that all terms halt with a unique, well formed value.

I've come across non-Turing complete languages primarily with proof assistants. When you're using programs to prove theorems, you need to make sure that all terms halt, since otherwise you can produce non-terminating terms of type False. This also ensures that type checking is decidable with dependent types, since we need to evaluate code with type checking. Agda and Coq are both languages that are not Turing Complete. This also ensures that you can't accidentally write an infinite loop, which is the motivation behind things like the Dhall language.

As for what you mention about program analysis, Rice's theorem means that any analysis of a Turing Complete language is either unsound or incomplete. So if you use restricted languages, you might be able to write analyses that are precise.

  • $\begingroup$ My area is in databases. Relational algebra, for example is not turing complete. And there are supposedly other sublanguages which are proper subset of relational algebra - that is, they are more 'niche'. What does it say about optimizations? $\endgroup$ – Zeruno Jun 18 '19 at 18:12
  • $\begingroup$ @Zeruno Not my area but I'm guessing it fulfills both "we don't want things to accidentally run forever" and " it makes analysis and optimization easier". Generally you want to use the weakest language that is powerful enough to do what you want. $\endgroup$ – jmite Jun 18 '19 at 20:00
  • $\begingroup$ "Weakest" in terms of expressive power? What is the optimization you are referring to in your question? $\endgroup$ – Zeruno Jun 19 '19 at 4:32
  • $\begingroup$ Weakest in terms of computability. I don't know databases specifically so I can't say what optimizations are possible there, but I can say for certain that fully optimizing is impossible I'd your language is Turing Complete. $\endgroup$ – jmite Jun 19 '19 at 5:42
  • $\begingroup$ Is the implication then that fully optimizing on a non-turing complete language is possible or even more likely to happen? $\endgroup$ – Zeruno Jun 19 '19 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.