सामग्री पर जाएँ
The Lumenary
स्नातक (उन्नत)Computationनियोजित

The λ-calculus

The untyped λ-calculus (terms, β-reduction, Church encodings, fixed-point combinators, confluence) and the simply typed λ-calculus with normalisation.

math.comp.lambda-calculus

इस विषय तक पहुँचने के लिए आवश्यक सब कुछ दिखाएँ

इस विषय का पाठ अभी लिखा नहीं गया है। नीचे दी गई रूपरेखा पाठ्यक्रम-मानचित्र का हिस्सा है और इसकी समीक्षा नहीं हुई है।

इस पर आधारित

Programming for mathematicsProof: direct, contrapositive, contradiction and induction

15 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)

आप सीखेंगे

  • Reduce λ-terms and encode booleans, pairs and natural numbers (Church numerals).
  • Use a fixed-point combinator to define recursive functions, and explain why untyped terms need not terminate.
  • State the Church–Rosser theorem and explain why every simply typed term has a normal form.

परिभाषा

  • λ-terms are built from variables by application (M N) and abstraction (λx. M).
  • β-reduction rewrites (λx. M) N to M[N/x], using capture-avoiding substitution.
  • A term is in normal form if no β-reduction applies to it.

प्रमेय

  • Church–Rosser: β-reduction is confluent, so a term has at most one normal form.
  • The untyped λ-calculus computes exactly the partial recursive functions.
  • Every simply typed λ-term has a normal form; in fact the simply typed λ-calculus is strongly normalising.

आम भ्रांतियाँ

  • Substituting without renaming bound variables (variable capture).
  • Thinking every λ-term has a normal form; (λx. x x)(λx. x x) does not.

आगे ले जाता है

Type theory and propositions as typesFormal methods

वैकल्पिक खोजें

अधिगम पथ

आगे पढ़ने के लिए

  • H. P. Barendregt, The Lambda Calculus: Its Syntax and Semantics (1981)
  • J. Roger Hindley and Jonathan P. Seldin, Lambda-Calculus and Combinators: An Introduction (2008)
  • Benjamin C. Pierce, Types and Programming Languages (2002)