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.
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
y, then the correct minimal reduction of
(W f x)is:
(W f x) = (W f y) (1) = f y y (2)
(W f x) = f x x (1) = f y x (2) = f y y (3)
Standard loopholes apply.
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.
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!