Various computational hierarchies describes the relative expressivity of different classes of languages, machines, or other models of computing, with the classic progression for Automata Theory [0] being: Deterministic Finite Automata (DFA) < Push-Down Automata (PDA) < Turing Machines (TM). These correspond to the following containment relations in the Computability hierarchy [1] of languages: Regular < Context-Free (CF) < Recursively Enumerable (RE).
Turing Complete programming languages are of computability class RE, and thus correspond to the automata class TM. However, for a given Turing Complete programming language, for example the Lambda Calculus, different evaluation strategies [2] can be specified which affect its behavior. In particular, there are expressions that can be reduced via lazy evaluation that cannot be reduced using a strict evaluation strategy [3]. Furthermore, between CF and RE is another computability class, the Recursive (R) languages [4]. These correspond to total functional programming languages [5], and the automata class of decidable Turing Machines (those which always halt) [6]. The set of reducible expressions of a total language is not affected by the choice of evaluation strategy. Indeed, if it is provable that all expressions can be reduced to identical normal forms under both lazy and strict strategies, then a language can be proven to be total, that is, in R and not RE. Thus, the behavior of a language under different evaluation strategies can be relevant to determining its computability classification.
What then is the computability relation between a given recursively enumerable language L equipped with lazy evaluation, and the same language equipped with strict evaluation? L is contained in RE. Would it be correct to say that L+LE and L+SE are both contained in RE? That L+SE < L+LE? What about other evaluation strategies? Does the Computational Complexity hierarchy capture these distinctions?
One can also consider this from the viewpoint of pure versus impure relational logic programming, e.g. minikanren or Prolog without and with the cut operator, respectively. Pure relational minikanren is a Turing Complete (RE) language, but certain programs that would halt when written with impure operators do not halt when written in pure style. What hierarchy of expressivity captures this behavior? In some respects Pure mk = Impure mk (because both are contained in RE), but in others Pure mk < Impure mk, because of the incidence of divergence in pure style programs.
References:
[0] https://en.wikipedia.org/wiki/Automata_theory
[1] https://en.wikipedia.org/wiki/Computability_theory
[2] https://en.wikipedia.org/wiki/Evaluation_strategy
[3] "And with certain programs the number of steps may be much smaller, for example a specific family of lambda terms using Church numerals take an infinite amount of steps with call-by-value (i.e. never complete), an exponential number of steps with call-by-name, but only a polynomial number with call-by-need."
https://en.wikipedia.org/wiki/Lazy_evaluation#Performance
[4] https://en.wikipedia.org/wiki/Recursive_language
[5] https://en.wikipedia.org/wiki/Total_functional_programming