Results 1 to 2 of 2

Math Help - Lambda calculus: S-problem: not quite seeing the pattern

  1. #1
    Member
    Joined
    Aug 2011
    Posts
    76
    Thanks
    1

    Lambda calculus: S-problem: not quite seeing the pattern

    So, I'm wading through the practice problems in Davie's chapter on Lambda Calculus, and he throws this one at me:

    reduce the following λ-expression to normal form:

    S (S S) (S S) (S S) S S

    where S = λ x y z . x z (y z)
    So, I tried to do this just by substituting and following the rules (fortunately I had already calculated S (S S) and (S S)). But by about the third piece of paper I lost track of the parenthesis and gave up. I threw it into a lambda calculator which used 1079 steps to produce a result that was over 15 lines long.

    Now, likely Davie didn't intend to give me 5 hours of busy work, so presumably there is some pattern or short cut I am supposed to be seeing here. Does anyone have any insight they could share that would be beneficial to me here?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Lambda calculus: S-problem: not quite seeing the pattern

    I tried a couple of calculators and I got results similar to yours. It may be that different reduction strategies (call-by-name, call-by-value, etc.) would give very different number of steps, but the final expression seems indeed long and impractical to write by hand.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pattern Problem
    Posted in the Algebra Forum
    Replies: 8
    Last Post: October 4th 2011, 10:24 AM
  2. Lambda Calculus: Bad Definition of Scope?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 7th 2011, 11:20 AM
  3. Pattern block problem
    Posted in the Geometry Forum
    Replies: 0
    Last Post: November 29th 2010, 06:27 PM
  4. Help with pattern problem
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: August 4th 2010, 02:38 AM
  5. Lambda calculus
    Posted in the Calculus Forum
    Replies: 3
    Last Post: February 13th 2009, 09:02 PM

Search Tags


/mathhelpforum @mathhelpforum