Turing Completeness - Non-Turing-complete Languages

Non-Turing-complete Languages

Many computational languages exist which are not Turing complete. One such example is the set of regular languages, most commonly regular expressions, which are generated by finite automata. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata and context-free grammars, which are commonly used to generate parse trees in an initial stage of program compiling. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions, or a series of mathematical formulae in a spreadsheet with no cycles.

In total functional programming languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory, whereas Epigram uses dependent types.