Editing Turing completeness (section)

==Non-Turing-complete languages==
Many computational languages exist that are not Turing-complete. One such example is the set of [[regular language]]s, which are generated by [[regular expression]]s and which are recognized by [[finite-state machine|finite automata]]. A more powerful but still not Turing-complete extension of finite automata is the category of [[pushdown automaton|pushdown automata]] and [[context-free grammar]]s, which are commonly used to generate parse trees in an initial stage of program [[compiler|compiling]]. Further examples include some of the early versions of the pixel shader languages embedded in [[Direct3D]] and [[OpenGL]] extensions.{{Citation needed|date=December 2010}}

In [[total functional programming]] languages, such as [[Charity (programming language)|Charity]] and [[Epigram (programming language)|Epigram]], all functions are total and must terminate. Charity uses a type system and [[control flow|control constructs]] based on [[category theory]], whereas Epigram uses [[dependent type]]s. The [[LOOP (programming language)|LOOP]] language is designed so that it computes only the functions that are [[primitive recursive function|primitive recursive]]. All of these compute proper subsets of the total computable functions, since the full set of total computable functions is not [[recursively enumerable set|computably enumerable]]. Also, since all functions in these languages are total, algorithms for [[recursively enumerable set]]s cannot be written in these languages, in contrast with Turing machines.

Although (untyped) [[lambda calculus]] is Turing-complete, [[simply typed lambda calculus]] is not.