0
$\begingroup$

Almost always in the study of computational complexity, the Turing machine is used as a model. On the other hand, the untyped lambda calculus is in a sense "simpler" than any Turing machine: there are only 2 fundamental rules of abstraction and application, in a sense dual to each other (as well as the introduction and elimination of implication in logic). This appears to be the simplest (and most abstract) model of computation ever created.

However, there is a problem with reduction: the "computational cost" of reduction varies depending on the computational strategy. For example, when duplicating a term, instead of recalculating, you can use references (which is, of course, some departure from the "purity" of the lambda calculus) and replace references to results. (Which, however, is not such a serious problem - it is quite possible to study the cost of reduction for different strategies separately).

However, there are some problems with Turing machines as well. First of all, this is that any particular Turing machine (and, more broadly, any finite automaton) always contains some "intrinsic complexity", which lies in the very structure of the machine. I'm afraid that this "intrinsic complexity" may have an unforeseen effect on the conclusions in the field of computational complexity. Does computational complexity research always use the same Turing machine model? Are there any conclusions for different models? If not, how can we be sure that the "intrinsic complexity" of a particular machine doesn't skew the results?

Another problem is the computational complexity of parallel computing. Lambda calculus has a natural parallelism that Turing machines don't have. Thus, the lambda calculus allows, for example, specifying the number of computational agents for several "computation branches" or modifying the concept of "computation time" (since in parallel computing, by increasing the number of computational agents, the time can be significantly reduced and even "jump" to another complexity class).

What do you think about it?

Thanks in advance.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This question ("What do you think about it?") is too vague. I'd suggest you reformulate your question to ask something more precise so you can get a useful answer. $\endgroup$
    – Max New
    Feb 13 at 18:53
  • 3
    $\begingroup$ There has been quite a lot of work on using $\lambda$-calculus in complexity theory, see e.g. P and NP classes explanation through lambda-calculus $\endgroup$
    – Martin Berger
    Feb 13 at 19:48

0

Reset to default

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.