![]() ![]() ![]() But what if you can use another encoding or even develop your own? In other words, can you give another set of definitions of one, two and sub in the Racket program so that: (define F (lambda (x) ((sub two) x))) The program above shows it's impossible when using Y as the solver in Church encoding. This makes the fixed-point combinator a generic tool for other problems that can be reducted to finding a fixed point. I am looking for a possibility of encoding the complexity in the problem not the solver. Everyone knows the answer is -b/a, so implementing this computation as a combinator in lambda calculus is a solution, but it is "fat". The solution should be first encoding F into lambda calculus then YF magically comes to be the correct answer. An example is solving ax + b = 0 by solving F(x) = (a+1)x + b = x. OTOH the most intuitive solution in my mind is a "thin" fixed-point combinator, which solves the linear equation by finding its fixed point. The currently known best solution is to translate the whole linear equation algorithm into lambda calculus that results in a "fat" combinator, and it is specific to linear equations not fixed points. If direct application of a fixed-point combinator (to the Church encoding of the linear equations) doesn't work, what is the most intuitive way of doing so in lambda calculus?Įdit. work means the combinator terminates on the input and returns a meaningful result.īecause lambda calculus is Turing-complete, it should be able to solve such equations (our computers can). How do we characterize the class of functions that work with these combinators?Įdit. So we know they work with some, but not all functions. Y and Z combinators work with G but not F. What is a high-level description of the reason why this method fails?Īre there other fixed-point combinators that can solve this equation? But after running this program, both Y and Z combinators enter an infinite loop (marked as err). If the combinator is clever, it may return one which is a solution. The way it tries to solve this problem is to define F(x) = 2 - x (in Church encoding) then use a combinator to compute its fixed point. ![]() ![]() Then it tries to find a solution to the arithmetic equation x = 2 - x using functional programming. (define G (lambda (_) (lambda (x) ((sub two) x))))Īs commented, this program first defines some numerals in Church encoding, some arithmetic operators on these numerals as well as Y and Z combinators. (define sub (lambda (m) (lambda (n) ((n pred) m)))) (define two (lambda (f) (lambda (x) (f (f x))))) (define one (lambda (f) (lambda (x) (f x)))) (define zero (lambda (f) (lambda (x) x))) The question is about this Racket program: #lang lazy ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |