Skip to main content
added 15 characters in body
Source Link
Marc
  • 696
  • 4
  • 12

A recent developpement on this topic: U. dal Lago and B. Accatoli proved that the length of the leftmost-outermost reduction (LOr) of a $\lambda$-term is an invariant (time) cost model for $\lambda$-calculus.

They show that turingTuring machines (with cost=time) and $\lambda$-terms (with cost=length of the LOr) can simulate each other with a polynomial overhead in time. So for instance the definisiondefinition of the class P does not depend on which of the two computation model you use to define it.

http://arxiv.org/abs/1405.3311

A recent developpement on this topic: U. dal Lago and B. Accatoli proved that the length of the leftmost-outermost reduction (LOr) of a $\lambda$-term is an invariant cost model for $\lambda$-calculus.

They show that turing machines (with cost=time) and $\lambda$-terms (with cost=length of the LOr) can simulate each other with a polynomial overhead. So for instance the definision of the class P does not depend on which of the two computation model you use to define it.

http://arxiv.org/abs/1405.3311

A recent developpement on this topic: U. dal Lago and B. Accatoli proved that the length of the leftmost-outermost reduction (LOr) of a $\lambda$-term is an invariant (time) cost model for $\lambda$-calculus.

They show that Turing machines (with cost=time) and $\lambda$-terms (with cost=length of the LOr) can simulate each other with a polynomial overhead in time. So for instance the definition of the class P does not depend on which of the two computation model you use to define it.

http://arxiv.org/abs/1405.3311

Source Link
Marc
  • 696
  • 4
  • 12

A recent developpement on this topic: U. dal Lago and B. Accatoli proved that the length of the leftmost-outermost reduction (LOr) of a $\lambda$-term is an invariant cost model for $\lambda$-calculus.

They show that turing machines (with cost=time) and $\lambda$-terms (with cost=length of the LOr) can simulate each other with a polynomial overhead. So for instance the definision of the class P does not depend on which of the two computation model you use to define it.

http://arxiv.org/abs/1405.3311