I get what a Turing machine is and what language is a Turing-complete language but when someone introduces me to a new programming language (like Solidity) and says it is Turing complete, what am I supposed to infer? What is the most important feature/advantage of a Turing complete? Is being Turing complete also a type of standard/benchmark for new languages?


closed as off-topic by Emil Jeřábek, Hsien-Chih Chang 張顯之, D.W., Jan Johannsen, Aryeh Jul 18 '18 at 10:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Hsien-Chih Chang 張顯之, D.W., Jan Johannsen, Aryeh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Some related half-troll: people are fine with finite automaton as long as finite is big enough :) cstheory.stackexchange.com/questions/2547/… $\endgroup$ – holf Jul 17 '18 at 15:54
  • $\begingroup$ The more important question here is: why should we use total (i.e. non-Turing complete) languages? $\endgroup$ – xrq Jul 17 '18 at 19:37

If a language is not Turing complete, there are computational problems it cannot solve. So, purely from a view internal to the language, you can't necessarily do everything you want. If you want to use a non-Turing complete language to design some kind of computer architecture, you'll also run into problems.

In order to express or simulate something that is Turing complete, your language needs to also be Turing complete. Python, C, and Java are all Turing Complete, so you can't write compilers for those languages in a language that isn't. The video games Minecraft and Dwarf fortress can simulate Turing machines, so you can't program those games in a language that isn't Turing complete. Powerpoint slide transitions are Turing complete, so you can't write Microsoft Office in a language that isn't Turing complete, or run it on a system that isn't Turing complete.

A programming language that isn't Turing complete isn't a "full programming language" in a sense, and someone who is telling you that a programming language is Turing complete is assuring you that this language can in fact do all of the things that the standard programming languages can.

  • $\begingroup$ Thanks, Stella! it makes a lot of sense. I was also wondering if there are any possible practical scenarios when one would prefer to use non-turning complete (or turning incomplete ) languages? $\endgroup$ – n0unc3 Jul 17 '18 at 16:19
  • $\begingroup$ Is it when halting/termination is an absoulte must ? $\endgroup$ – n0unc3 Jul 17 '18 at 16:20
  • $\begingroup$ Non-TC languages can be useful when it's important to be able to prove termination in many different contexts. In practical contexts you can usually "know" if it'll converge for your context even if you can't prove it in general. $\endgroup$ – Stella Biderman Jul 18 '18 at 19:46

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