Y Combinator is a concept in computer science and mathematics that represents a pure function expressing [[recursion]] within the Lambda Calculus. It was originally discovered by Haskell Curry and later popularized by mathematician [[Raymond M. Smullyan]]. In Lambda Calculus, functions are defined using only lambda expressions, which are anonymous functions that can be applied to arguments. However, Lambda Calculus lacks built-in support for recursion, making it difficult to define recursive functions directly. Before looking into Y Combinator, one can first look at what is recursion: [[recursion#An example of recursion]]. The Y Combinator provides a solution to this problem by enabling recursion in Lambda Calculus. It is a higher-order function that takes a function as an argument and returns its fixed point, i.e., the input function with its own invocation applied to itself. The Y Combinator can be defined using the following lambda expression: ``` Y = λf.(λx.f (x x)) (λx.f (x x)) ``` Here, f represents the function we want to make recursive. The Y Combinator applies f to itself by passing (x x) as an argument. This self-application creates the necessary recursion. By using the Y Combinator, recursive functions can be defined in Lambda Calculus without directly relying on any built-in recursion mechanisms. Y Combinator has applications beyond [[Lambda Calculus]] as well. It is used in functional programming languages like Scheme and Haskell to implement recursion and define recursive functions indirectly. Additionally, it plays a fundamental role in understanding concepts like fixed points and self-reference within computation theory. # References ```dataview Table title as Title, authors as Authors where contains(subject, "Y Combinator") ```