Languages and Machines

Aritra (invited, but not joined this community yet) once mentioned how he hates λ-calculus so much as compared to the Turing machine model, I did not have good arguments to convince him otherwise. This post helps presents the story from the other side. Two excerpts (tl;dr):

When confronted with this question, my typical colleague (at least on the theory side) dismisses the question as totally uninteresting because “all models of computation are polynomial-time equivalent”, so who cares? Well, if your work is all done modulo a polynomial factor in complexity, and you only care about computations over natural numbers (or other finitary objects), then I guess it doesn’t matter. You tell some story once and for all of how the objects of interest are represented on some model, and leave it at that; the details just don’t matter.

But obviously the models do matter, as evidenced by the inescapable fact that the very same colleague would never under any circumstance consider anything other than a classical machine model as the underpinning for his work! Surely, if they are all equivalent, then it can’t matter, so we can all switch to the λ-calculus, right? Well, true though that may be, I can assure you that your argument is going nowhere. Apparently some models are more equivalent than others after all! Why would that be?

There is an alternative, which is to provide a cost semantics for the language we write, and conduct our analyses on this basis directly , without appeal to a compiler or reference to an underlying machine. In short we adopt a linguistic model of computation, rather than a machine model , and life gets better! There is a wider range of options for expressing algorithms, and we simplify the story of how algorithms are to be analyzed.

To do this requires that we give a cost semantics for the language we’re actually using. And this is where the λ-calculus comes into play, for it is the paradigmatic example of how to specify a language-based model of computation. Briefly, the crucial notion in the λ-calculus is the concept of a reduction , written M→M’, expressing one step of computation of program M resulting in program M’. Execution is defined directly on the programs we write, and the model provides a well-defined notion of computation step that we can count to obtain the time complexity of the program. Decades of experience shows that this approach scales to realistic languages.

Haha I was only being half serious when I said that. Most of it was because of my frustration with teaching \lambda calculus to students.

Also, I definitely prefer \lambda-calculus over Turing machines mainly because of aesthetic reasons. Writing code using \lambda-calculus is easier and intuitive than designing Turing machines.

I also agree with the author of this post. I think a linguistic model of computation should be preferred over a machine model. But in complexity theory, we are forced to consider other models of computation many of which are very machine-like ( boolean circuits and arithmetic circuits for example). The reason being it is much easier to argue about lower bounds results using arithmetic circuits\boolean circuits than with linguistic models or uniform machine model like Turing machine.

1 Like

Do you think cost semantics that Bob talks about are insufficient for reasoning about (tight?) lower bounds?

PS: I realize the LaTeX/math isn’t rendering here. Let me quickly install and enable the math plugin for discourse, that will make it much smoother to talk technical stuff here. Should be ready in 10 minutes.

Edit (15 minutes later): Done!

Do you think cost semantics that Bob talks about are insufficient for reasoning about (tight?) lower bounds?

I think time complexity and lower bounds I’m talking about is different from what is being discussed in the article.

The article is talking about the time complexity of a single program or an algorithm. I think “cost semantics” is more than enough for this task.

When I mentioned lower bounds, I had something else in my mind. I was not talking about the lower bound of a single algorithm rather lower bound for a problem ( more precisely all algorithms solving a particular problem). For instance, If I have the SAT problem I want to show that there is no algorithm for SAT that run in polynomial time. These kind of lower bounds are extremely difficult because if you are reasoning about all algorithms that can solve a particular problem not just a single problem.

There are only a few lower bound results known because the problem is very hard. Majority of these lower bound results use non-uniform models of computation like boolean circuit models or arithmetic circuit models (these are not equivalent to Turing machines but they can imply results for Turing machines), Most important problems in complexity theory are open. So, we don’t really whether a particular method will work or not.

1 Like