Page "Functional programming" Paragraph 24

Most general purpose functional programming languages allow unrestricted recursion and are Turing complete, which makes the halting problem undecidable, can cause unsoundness of equational reasoning, and generally requires the introduction of inconsistency into the logic expressed by the language's type system.

Some special purpose languages such as Coq allow only well-founded recursion and are strongly normalizing ( nonterminating computations can be expressed only with infinite streams of values called codata ).

As a consequence, these languages fail to be Turing complete and expressing certain functions in them is impossible, but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion.

Functional programming limited to well-founded recursion with a few other constraints is called total functional programming.

See Turner 2004 for more discussion .< ref name = totalfp >