<p>Turing-machines and <span class="math-container">$\lambda$</span>-calculus are equivalent only w.r.t. the functions <span class="math-container">$\mathbb{N} \rightarrow \mathbb{N}$</span> they can define.</p>

<p>From the point of view of computational complexity they seem to behave differently.
The main reason people use Turing machines and not <span class="math-container">$\lambda$</span>-calculus to reason about
complexity is that using <span class="math-container">$\lambda$</span>-calculus naively leads to unrealistic complexity measures, because you can copy terms (of arbitrary size) freely in single <span class="math-container">$\beta$</span>-reduction steps, e.g. <span class="math-container">$(\lambda x.xxx)M \rightarrow MMM.$</span> In other words, single reduction steps in <span class="math-container">$\lambda$</span>-calculus are a lousy cost model. In contrast, single Turing-machine reduction steps  work great (in the sense of being good predictors of real-world program run-time).</p>

<p>It is not known how fully to recover
conventional Turing-machine based complexity theory in
<span class="math-container">$\lambda$</span>-calculus. In a <a href="http://arxiv.org/abs/1405.3311" rel="noreferrer">recent (2014) breakthrough Accattoli and Dal Lago</a>
managed to show  that
large classes of time-complexity such as <span class="math-container">$P$</span>, <span class="math-container">$NP$</span> and <span class="math-container">$EXP$</span> can
be given a natural <span class="math-container">$\lambda$</span>-calculus formulation. But smaller
classes like <span class="math-container">$O(n^2)$</span> or <span class="math-container">$O(n \, log\, n)$</span> cannot be presented
using the Accattoli / Dal Lago techniques.</p>

<p>How to recover conventional space   complexity using
<span class="math-container">$\lambda$</span>-calculus is unknown.</p>

CC BY-SA 3.0
2014-06-09T09:26:00.053Z
I feel the need to clarify here: there is no special "technique" Accattoli and Dal Lago use to "present" time classes. The presentation is the "naive" one: define $\lambda TIME(f(n))$ as the class of languages decidable by a $\lambda$-term in $f(n)$ $\beta$-reduction steps, under any standard reduction strategy (*e.g.* leftmost-outermost). Accattoli and Dal Lago showed, using techniques coming from linear logic, that there is a polynomial $p$ such that $\lambda TIME(f(n))=TIME(p(f(n))$.
Damiano Mazza
CC BY-SA 3.0
2014-06-09T10:36:34.037Z
@DamianoMazza Yes that's right, what I meant is that I don't think the techniques used to show this result can be used to show e.g. $\lambda TIME(n^2) = TIME(n^2)$.
Martin Berger
CC BY-SA 3.0
2014-06-09T21:01:39.780Z
Ok, I see. Actually, my guess is that $\lambda TIME(n^2)\neq TIME(n^2)$: complexity classes such as $TIME(n^2)$ or $TIME(n\log n)$ are not robust, one cannot expect them to be stable under changes in the computational model (this is notoriously the case even if we stick to Turing machines, *e.g.* single-tape vs. multi-tape).
Damiano Mazza
CC BY-SA 3.0
2014-06-09T21:41:35.093Z
@DamianoMazza I agree, likewise for the size of the chosen alphabet.  But an
algorithm running in $f(n)$ on an $n$-tape machine can be simulated in
$5kf^2(n)$ on a 1-tape machine, a modest quadratic blowup. What's the
blowup of the current translation of Accattoli and Dal Lago's? I don't
remember if they explicitly state it.
Martin Berger
CC BY-SA 3.0
2014-06-10T19:02:41.843Z
The cost of copying *IS* fast on a graph reduction machine. All nodes referencing X point to X. X is then made to be M. So I think the example given is rather bad.
Jake
CC BY-SA 3.0
2014-06-11T07:58:53.837Z
@Jake Graph rewriting is not $\lambda$-calculus. It's a different model of computing that you can use
to implement $\lambda$-calculus. Indeed the Accattoli and Dal Lago paper uses clever sharing to establish their result.
Martin Berger
CC BY-SA 3.0
2017-01-18T19:08:39.087Z
@Jake The cited paper discusses beta-normalization (see page two). Similar results were already known for other forms of reduction, like weak reduction (that is, call-by-value)—see Dal Lago & Martini, 2008 (discussed in that paper and in http://cstheory.stackexchange.com/a/397/989).
Blaisorblade
CC BY-SA 4.0
2014-06-06T09:08:28.767Z
2019-01-23T09:01:43.013Z
2019-01-23T09:01:43.013Z
Martin Berger
<p>I paste part of <a href="https://cstheory.stackexchange.com/questions/21705/what-is-the-contribution-of-lambda-calculus-to-the-field-of-theory-of-computatio/21713#21713">an answer I wrote for another question</a>:</p>

<blockquote>
  <p>Implicit Computational Complexity aims at characterizing complexity classes by means of dedicated languages. The first results such as <em>Bellantoni-Cook's Theorem</em> were stated in terms of $\mu$-recursive functions, but more recent results use the vocabulary and techniques of $\lambda$-calculus. See this <a href="http://link.springer.com/chapter/10.1007/978-3-642-31485-8_3" rel="noreferrer">Short introduction to Implicit Computational Complexity</a> for more and pointers, or the proceedings of the <a href="http://perso.ens-lyon.fr/patrick.baillot/DICE/" rel="noreferrer">DICE workshops</a>.</p>
</blockquote>

<p>There exist characterizations of (at least) $\mathsf{FP}$ by means of $\lambda$-calculus.</p>

CC BY-SA 3.0
2014-06-06T08:29:53.873Z
2014-06-06T08:29:53.873Z
2017-04-13T12:32:28.080Z
Bruno
<p>I don't know if this answers (part of) your question but there are indeed alternative characterizations of the complexity classes (esp. <span class="math-container">$\mathbb{P}$</span> and <span class="math-container">$\mathbb{NP}$</span>) in terms of logics (1st order logic, 2nd order logic, etc..).</p>

<p>For example the <a href="http://en.wikipedia.org/wiki/Second-order_logic#Relation_to_computational_complexity" rel="nofollow noreferrer">work</a> of <a href="http://en.wikipedia.org/wiki/Fagin%27s_theorem" rel="nofollow noreferrer">R. Fagin</a> (et al.) in this <a href="http://en.wikipedia.org/wiki/Descriptive_complexity" rel="nofollow noreferrer">area</a> is notable (and imo might provide insight related to the <span class="math-container">$\mathbb{P}$</span> vs <span class="math-container">$\mathbb{NP}$</span> issue and relations with descriptive and <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow noreferrer">algorithmic</a> complexity)</p>

<p>Some further characterizations of computational complexity classes in terms of algorithmic (Kolmogorov-Solomonov) complexity can be found (for example) <a href="http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf" rel="nofollow noreferrer">here</a> and <a href="http://www.researchgate.net/publication/48309221_Using_Randomness_to_Characterize_the_Complexity_of_Computation" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2014-06-09T20:49:44.710Z
2019-01-23T08:23:53.100Z
2019-01-23T08:23:53.100Z
Nikos M.
<p>In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of computation are equivalent (and if we can introduce anything in terms Turing machine, we can introduce this in terms any model of computation), but I never seen explanation idea P and NP complexity classes through lambda-calculus.
Can anybody explain notions P and NP complexity classes without Turing machine and only with lambda calculus as model of computation.</p>

CC BY-SA 3.0
2014-06-06T09:17:20.713Z
Their computational power is equivalent only for functions over natural numbers, not higher types or other settings.
Kaveh
CC BY-SA 3.0
2014-06-06T23:19:08.543Z
[Turing completeness](http://en.wikipedia.org/wiki/Turing_completeness) is sometimes a more theoretical concept to show a connection but more applied "conversions" between TM complete systems are not always actually carried out in practice ie its sometimes more about existence proofs...
vzn
<cc.complexity-theory><complexity-classes><turing-machines><lambda-calculus>
P and NP classes explanation through lambda-calculus
Simplex
# P and NP classes explanation through lambda-calculus

(Asked by: username_0 on 2014-06-06)

In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of computation are equivalent (and if we can introduce anything in terms Turing machine, we can introduce this in terms any model of computation), but I never seen explanation idea P and NP complexity classes through lambda-calculus.
Can anybody explain notions P and NP complexity classes without Turing machine and only with lambda calculus as model of computation.

**Tags:** cc.complexity-theory, complexity-classes, turing-machines, lambda-calculus
> **Comments:**
> **username_1**: Their computational power is equivalent only for functions over natural numbers, not higher types or other settings.  
> **username_2**: [Turing completeness](http://en.wikipedia.org/wiki/Turing_completeness) is sometimes a more theoretical concept to show a connection but more applied "conversions" between TM complete systems are not always actually carried out in practice ie its sometimes more about existence proofs...  

---

## 3 answers

### Answer by username_3 on 2014-06-06. Score: 48

Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define.

From the point of view of computational complexity they seem to behave differently.
The main reason people use Turing machines and not $\lambda$-calculus to reason about
complexity is that using $\lambda$-calculus naively leads to unrealistic complexity measures, because you can copy terms (of arbitrary size) freely in single $\beta$-reduction steps, e.g. $(\lambda x.xxx)M \rightarrow MMM.$ In other words, single reduction steps in $\lambda$-calculus are a lousy cost model. In contrast, single Turing-machine reduction steps work great (in the sense of being good predictors of real-world program run-time).

It is not known how fully to recover
conventional Turing-machine based complexity theory in
$\lambda$-calculus. In a [recent (2014) breakthrough Accattoli and Dal Lago](http://arxiv.org/abs/1405.3311)
managed to show that
large classes of time-complexity such as $P$, $NP$ and $EXP$ can
be given a natural $\lambda$-calculus formulation. But smaller
classes like $O(n^2)$ or $O(n \, log\, n)$ cannot be presented
using the Accattoli / Dal Lago techniques.

How to recover conventional space complexity using
$\lambda$-calculus is unknown.

> **Comments:**
> **username_4**: I feel the need to clarify here: there is no special "technique" Accattoli and Dal Lago use to "present" time classes. The presentation is the "naive" one: define $\lambda TIME(f(n))$ as the class of languages decidable by a $\lambda$-term in $f(n)$ $\beta$-reduction steps, under any standard reduction strategy (*e.g.* leftmost-outermost). Accattoli and Dal Lago showed, using techniques coming from linear logic, that there is a polynomial $p$ such that $\lambda TIME(f(n))=TIME(p(f(n))$.  
> **username_3**: @DamianoMazza Yes that's right, what I meant is that I don't think the techniques used to show this result can be used to show e.g. $\lambda TIME(n^2) = TIME(n^2)$.  
> **username_4**: Ok, I see. Actually, my guess is that $\lambda TIME(n^2)\neq TIME(n^2)$: complexity classes such as $TIME(n^2)$ or $TIME(n\log n)$ are not robust, one cannot expect them to be stable under changes in the computational model (this is notoriously the case even if we stick to Turing machines, *e.g.* single-tape vs. multi-tape).  
> **username_3**: @DamianoMazza I agree, likewise for the size of the chosen alphabet.  But an algorithm running in $f(n)$ on an $n$-tape machine can be simulated in $5kf^2(n)$ on a 1-tape machine, a modest quadratic blowup. What's the blowup of the current translation of Accattoli and Dal Lago's? I don't remember if they explicitly state it.  
> **username_5**: The cost of copying *IS* fast on a graph reduction machine. All nodes referencing X point to X. X is then made to be M. So I think the example given is rather bad.  
> **username_3**: @Jake Graph rewriting is not $\lambda$-calculus. It's a different model of computing that you can use to implement $\lambda$-calculus. Indeed the Accattoli and Dal Lago paper uses clever sharing to establish their result.  
> **username_6**: @Jake The cited paper discusses beta-normalization (see page two). Similar results were already known for other forms of reduction, like weak reduction (that is, call-by-value)—see Dal Lago & Martini, 2008 (discussed in that paper and in http://cstheory.stackexchange.com/a/397/989).  

---

### Answer by username_7 on 2014-06-06. Score: 13

I paste part of [an answer I wrote for another question](https://cstheory.stackexchange.com/questions/21705/what-is-the-contribution-of-lambda-calculus-to-the-field-of-theory-of-computatio/21713#21713):

> Implicit Computational Complexity aims at characterizing complexity classes by means of dedicated languages. The first results such as *Bellantoni-Cook's Theorem* were stated in terms of $\mu$-recursive functions, but more recent results use the vocabulary and techniques of $\lambda$-calculus. See this [Short introduction to Implicit Computational Complexity](http://link.springer.com/chapter/10.1007/978-3-642-31485-8_3) for more and pointers, or the proceedings of the [DICE workshops](http://perso.ens-lyon.fr/patrick.baillot/DICE/).

There exist characterizations of (at least) $\mathsf{FP}$ by means of $\lambda$-calculus.


---

### Answer by username_8 on 2014-06-09. Score: 6

I don't know if this answers (part of) your question but there are indeed alternative characterizations of the complexity classes (esp. $\mathbb{P}$ and $\mathbb{NP}$) in terms of logics (1st order logic, 2nd order logic, etc..).

For example the [work](http://en.wikipedia.org/wiki/Second-order_logic#Relation_to_computational_complexity) of [R. Fagin](http://en.wikipedia.org/wiki/Fagin%27s_theorem) (et al.) in this [area](http://en.wikipedia.org/wiki/Descriptive_complexity) is notable (and imo might provide insight related to the $\mathbb{P}$ vs $\mathbb{NP}$ issue and relations with descriptive and [algorithmic](http://en.wikipedia.org/wiki/Kolmogorov_complexity) complexity)

Some further characterizations of computational complexity classes in terms of algorithmic (Kolmogorov-Solomonov) complexity can be found (for example) [here](http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) and [here](http://www.researchgate.net/publication/48309221_Using_Randomness_to_Characterize_the_Complexity_of_Computation).


---

