Non Turing Complete Programming Languages

In this article, we have explored the idea of Non Turing Complete Programming Languages and listed all examples of Non Turing Complete Programming Languages along with advantages of such languages.

Table of contents:

  1. Non Turing Complete Programming Languages
  2. Need of Non Turing Complete Programming Languages
  3. Conclusion

Non Turing Complete Programming Languages

Non-Turing Complete Programming Language means there exist computations which cannot be implemented using these Programming Languages. This is also known as Turing Incomplete language.

In simple terms, Turing Complete means any computation can be implemented in a Turing Machine. So, Non Turing Complete Programming Language cannot implement all kind of algorithms.

Non Turing Complete Programming Languages

The most common Programming Languages like Java, C++, C, Rust, GoLang, Python and others are Turing Complete Programming Languages.

Example of Programming Languages that are not Turing Complete are:

  • SQL92
  • BNF
  • Regular expressions (Regex)
  • Berkley Packet Filter (BPF) Bytecode
  • HTML
  • XML
  • JSON
  • YAML
  • Markdown
  • BlooP (Bounded Loop) Programming Language is a Non Turing Complete Programming Language. It has one limitation that is every loop must have a limit on the number of iterations that is infinite loop is not allowed. Halting Problem can be solved using programs using BlooP language.
  • Charity Programming Language is a Non Turing Complete Programming Language that can solve difficult problems like Hanoi Tower and Ackermann Function.

Data Languages like HTML, XML, JSON and Markdown are always Non Turing Complete Programming Languages as they are designed to represent data and not computation.

Note that declarative SQL and Procedural extensions of SQL are Turing Complete. Only SQL92 is not Turing Complete. Similarly, Lambda Calculus is Trung Complete but its variants like Typed Lambda Calculus and System F are not.

Need of Non Turing Complete Programming Languages

Non Turing Complete Programming Languages are quite useful in real life applications and are the preferred choice for safe and restricted systems. The applications of Non Turing Complete Programming Languages are:

  • Adding restrictions in a Programming Language to make a particular task/ implementation impossible
  • To guarantee termination of implementation
  • Simplify code by eliminating possibility of runtime error

This paper titled "Total Functional Programming" by D. A. Turner from Middlesex University, UK explains why restricted languages (like non functional programming languages) are preferred as guarantees of Compiler are strong but proving limitations of languages are much convinient.

Conclusion

Non Turing Complete Programming Languages are uncommon yet very powerful to impose restrictions on a system and avoid unexpected situations.

Every serious Programmer should give a Non Turing Complete Programming Language a try to understand its power.