2
$\begingroup$

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

[6] https://en.wikipedia.org/wiki/Decider_(Turing_machine)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Most (or all) reasonable programming are Turing-complete, and thus can be used to compute exactly the computable functions, i.e., to decide the decidable languages, nothing more and nothing less. So details like strict or lazy evaluation don't make a difference to their expressiveness, in this sense.

a given recursively enumerable language L equipped with lazy evaluation

This is a fundamental misunderstanding. There are two meanings of the word "language" in computer science.

One meaning is a formal language: a subset of $\{0,1\}^*$. See https://en.wikipedia.org/wiki/Formal_language#Definition. A formal language can be recursively enumerable or not.

Another meaning is a programming language: a way of expressing computer programs. See https://en.wikipedia.org/wiki/Programming_language. A programming language can use lazy evaluation or strict evaluation or neither.

It makes no sense to mix these two. Even though both use the same word ("language") in their name, they are fundamentally different concepts.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Please see this related question for a concrete example where the set of accessible normal terms is dependent on the choice of evaluation strategy: cs.stackexchange.com/questions/153466/… $\endgroup$
    – jpt4
    Aug 7, 2022 at 23:49
  • $\begingroup$ I agree that Turing Complete languages all occupy the same class of computational expressivity as measured by various extant hierarchies. However, consider the difference between the hierarchies of computability and computational complexity: the former makes no distinction between classes on the basis of resource usage, while the latter does. Introducing a sensitivity to resource usage enables finer-grained classification, without invalidating the coarser-grained perspective. Thus, I am curious whether a sensitivity to evaluation strategies induces an analogous increase in resolution. $\endgroup$
    – jpt4
    Aug 7, 2022 at 23:54
  • $\begingroup$ @jpt4, You asked about "the computability relation". "Computability" has a specific meaning. $\endgroup$
    – D.W. ♦
    Aug 8, 2022 at 0:02
  • $\begingroup$ As per my question, there are "various computational hierarchies" used to capture the expressiveness of computing systems. I provide examples of two, Automata Theory and Computability Theory, which are different, yet can be placed in correspondence with each other. This motivates the inquiry as to whether another hierarchy is possible, which focuses on other aspects of computation, in this case evaluation strategy. Does this hierarchy exist? ("Does the Computational Complexity hierarchy capture these distinctions?" "What hierarchy of expressivity captures this behavior?") $\endgroup$
    – jpt4
    Aug 8, 2022 at 0:09
  • $\begingroup$ @jpt4, we have a rule/expectation that you ask only one question per post. I count about 5-6 questions in your post. It appears that I answered one of those questions, but that wasn't the one you most wanted answered and you aren't finding this answer satisfying, which for me illustrates one of the issues with posts that ask more than one question. I hope you find some other responses that you find more helpful! $\endgroup$
    – D.W. ♦
    Aug 8, 2022 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.