views:

121

answers:

2

I'm reading an article about different evaluation strategies (I linked article in wiki, but I'm reading another one not in English). And it says that unlike to call-by-name and call-by-need strategies, call-by-value strategy is not Turing complete.

Can anybody explain, please, why is it so? If it's possible, add an example pls.

+9  A: 
Norman Ramsey
A: 

Your question doesn't make a lot of sense without reference to some specific language, but I'll try my best to answer with respect to the Untyped Lambda calculus.

The existence of a call-by-value fixed point combinator (i.e. "Y combinator") for the untyped lambda calculus seems to refute the basic claim (see: Fixed Point Combinator). The existence of such a combinator breaks strong normalization, which suggests that there is at least one language that is turing complete that uses a call-by-value evaluation strategy.

Much more likely to affect the turing-completeness of a language is the existence (or lack of) a type system. For example, the simply-typed lambda calculus cannot encode a fixed point combinator, and is strongly normalising (i.e. all well-typed terms reduce to a value), however, this is true irrespective of the evaluation strategy employed. Rather, it is a consequence of the type system.

Gian