Skip to main content
edited tags
Link
Bubbler
  • 78.4k
  • 5
  • 149
  • 469
edited tags
Link
user62131
user62131
Clarification on length < 100
Source Link
ThreeFx
  • 1.5k
  • 9
  • 22

#Background#

You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:

(S I I (S I I))

You notice that when trying to reduce it to its normal form, it reduces to itself after three steps:

(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

You are determined to find other expressions which share this trait and begin to work on this immediately.

Rules

  • You may use any combination of the following combinators:

      B f g x = f (g x)
      C f x y = f y x
      I x     = x
      K x y   = x
      S f g x = f x (g x)
      W f x   = f x x
    
  • Application is left associative, which means that (S K K) is actually ((S K) K).

  • A reduction is minimal there is no other order of reduction steps which uses fewer steps. Example: if x has reduction y, then the correct minimal reduction of (W f x) is:

      (W f x)
      = (W f y) (1)
      = f y y   (2)
    

    and not

      (W f x)
      = f x x   (1)
      = f y x   (2)
      = f y y   (3) 
    
  • Standard loopholes apply.

Task

We define the cycle of an expression to be the minimal number of reductions in between two same expressions.

Your task is to find the expression, with lengththe number of combinators used < 100, which produces the longest cycle.

Scoring

Your score will be determined by the length of the cycle of your expression. If two people's expression have the same cycle, the answer which uses fewer combinators wins. If they both use the same number of combinators, the earlier answer wins.

Good luck and have fun!

#Background#

You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:

(S I I (S I I))

You notice that when trying to reduce it to its normal form, it reduces to itself after three steps:

(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

You are determined to find other expressions which share this trait and begin to work on this immediately.

Rules

  • You may use any combination of the following combinators:

      B f g x = f (g x)
      C f x y = f y x
      I x     = x
      K x y   = x
      S f g x = f x (g x)
      W f x   = f x x
    
  • Application is left associative, which means that (S K K) is actually ((S K) K).

  • A reduction is minimal there is no other order of reduction steps which uses fewer steps. Example: if x has reduction y, then the correct minimal reduction of (W f x) is:

      (W f x)
      = (W f y) (1)
      = f y y   (2)
    

    and not

      (W f x)
      = f x x   (1)
      = f y x   (2)
      = f y y   (3) 
    
  • Standard loopholes apply.

Task

We define the cycle of an expression to be the minimal number of reductions in between two same expressions.

Your task is to find the expression, with length < 100, which produces the longest cycle.

Scoring

Your score will be determined by the length of the cycle of your expression. If two people's expression have the same cycle, the answer which uses fewer combinators wins. If they both use the same number of combinators, the earlier answer wins.

Good luck and have fun!

#Background#

You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:

(S I I (S I I))

You notice that when trying to reduce it to its normal form, it reduces to itself after three steps:

(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

You are determined to find other expressions which share this trait and begin to work on this immediately.

Rules

  • You may use any combination of the following combinators:

      B f g x = f (g x)
      C f x y = f y x
      I x     = x
      K x y   = x
      S f g x = f x (g x)
      W f x   = f x x
    
  • Application is left associative, which means that (S K K) is actually ((S K) K).

  • A reduction is minimal there is no other order of reduction steps which uses fewer steps. Example: if x has reduction y, then the correct minimal reduction of (W f x) is:

      (W f x)
      = (W f y) (1)
      = f y y   (2)
    

    and not

      (W f x)
      = f x x   (1)
      = f y x   (2)
      = f y y   (3) 
    
  • Standard loopholes apply.

Task

We define the cycle of an expression to be the minimal number of reductions in between two same expressions.

Your task is to find the expression, with the number of combinators used < 100, which produces the longest cycle.

Scoring

Your score will be determined by the length of the cycle of your expression. If two people's expression have the same cycle, the answer which uses fewer combinators wins. If they both use the same number of combinators, the earlier answer wins.

Good luck and have fun!

Tweeted twitter.com/#!/StackCodeGolf/status/555908091062267904
fixed ambiguity in reduction steps
Source Link
ThreeFx
  • 1.5k
  • 9
  • 22
Loading
added associativity to clarify application
Source Link
ThreeFx
  • 1.5k
  • 9
  • 22
Loading
edited tags
Link
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975
Loading
Source Link
ThreeFx
  • 1.5k
  • 9
  • 22
Loading