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?

  • 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
    Commented Jul 17, 2018 at 15:54
  • $\begingroup$ The more important question here is: why should we use total (i.e. non-Turing complete) languages? $\endgroup$
    – xrq
    Commented Jul 17, 2018 at 19:37

1 Answer 1


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
    Commented Jul 17, 2018 at 16:19
  • $\begingroup$ Is it when halting/termination is an absoulte must ? $\endgroup$
    – n0unc3
    Commented Jul 17, 2018 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$ Commented Jul 18, 2018 at 19:46

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