I have a lambda expression: λx.λy.x(xy), and I'm supposed to infer the integer representation of it. I've read a lot about Church encodings and Church numerals specifically but I can't find what number is. Can you explain it to me in a way a 3 year old can understand or refer me to a resource better than wikipedia?
can't deduce the numeral representation (church encoding) of a lambda expression λx.λy.x(xy)
200 Views Asked by matos416 At
1
There are 1 best solutions below
Related Questions in LAMBDA-CALCULUS
- How could this Y' same as this Y combinator itself?
- Type information system recovery
- mock - church numerals?
- beta-equivalence, beta-reduction and transitive+reflexive beta-reduction
- Overlapping Days Calculation Nightmare
- Lambda Calculus - Evaluating Custom Rewrite Rules to Increment
- Is it possible, using PHOAS, to evaluate a term to normal form, and then stringify it?
- Are numbers also functions in functional programming?
- Valid Lambda Expressions
- 'Segmentation Fault' occurred when Lambda Function in Python recurves over 1e5 times
- Why Rust fails when I try to implement recursion with "S I I" from SKI-calculus?
- Do you multiply or add when simplifying λ-expressions?
- How does "true" evaluate in the lazy lambda calculus?
- What is (Y Y), the Y-combinator applied to itself?
- How to prove Theorem euclid_gcd : forall a b z, euclid a b z -> gcd a b z. using coq?
Related Questions in CHURCH-ENCODING
- mock - church numerals?
- church number in rust
- Sum/product of Church-encoded list of numbers does not type check
- How to encode two distinct Unit types using church encoding
- Church numerals, rigid type and infinite type
- How to revert beta-reductions to named functions in a lambda calculus-based system?
- Going from Curry-0, 1, 2, to ...n
- Understanding church numerals
- How to iterate or repeat untyped function n times?
- Defining a function to represent integers in Church numerals (DrRacket)
- How to define a function with Church numerals in lambda-terms?
- How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?
- How to return the Church number
- unfolding recursive expressions
- How to make a function call itself n times
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Church encoding of integers is the following:
"0" ≡ (λf.(λx.x)): Think of(λf.(λx.x))as meaning: given a functionfand an elementx, the result isx: it's like applying the functionfzero times tox."1" ≡ (λf.(λx.(fx))): Think of(λf.(λx.(fx)))as meaning: given a functionfand an elementx, the result is(fx): which should be thought of as applyftoxor, in more standard mathematical notation, like f(x)."2" ≡ (λf.(λx.(f(fx)))): Think of(λf.(λx.(f(fx))))as meaning: given a functionfand an elementx, the result is(f(fx)): which should be thought of as applyftoxtwice or, in more standard mathematical notation, like f(f(x))."3" ≡ (λf.(λx.(f(f(fx))))): Think of(λf.(λx.(f(f(fx)))))as meaning: given a functionfand an elementx, the result is(f(f(fx))): which should be thought of as applyftoxthree times or, in more standard mathematical notation, like f(f(f(x))).I hope that you see the pattern (and the logic behind). In your case,
(λx.(λy.(x(xy))))is the Church encoding of the number2(using alpha-equivalence, of course).The wikiped article is actually quite clear. What is it that you don't understand?