Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

读物

• Sylvain Salvari. Lambda Calculus and Formal Language Theory. Wenbo suggested.
• Computability and Complexity From a Programming Perspective A commonly used model of computation is the lambda calculus [?], [?]. It is, however, seldom used in complexity texts as the notion of a computation cost is unclear. This isboth because the number of reduction steps depends heavily on the reduction strategyused and because the basic reduction step in the lambda calculus –β-reduction – is considered too complex to be an atomic computation step.

A063573 Counts the number S(n) of lambda terms at level n, in the case of a single variable.

• Let V be the number of variables.
• {$S(n+1) = VS(n) + 2S(n)\sum_{i=0}^{n-1}S(i) + S(n)S(n)$}
• This comes from two steps.
  • Add {$\lambda x.\_ $} in front of a lambda term from level n.
  • Combine two lambda terms {$( \_\;\_ )$} at least one of which comes from {$S(n)$}.
  • When V=1 we get 1,2,10,170,33490...
  • When V=2 we get 2,8,112,15008...

Calculate the combinatorics of the lambda-calculus on a single variable, and if possible, on two or more variables. Is the lambda-calculus equivalent to the recursion relation for orthogonal polynomials?