13
\$\begingroup\$

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!

Improve this question
\$\endgroup\$
13
  • \$\begingroup\$ atomic-code-golf would fit for your tie breaker, but I wouldn't add a tag for the tie breaker. If there's not appropriate tag, then the default is code-challenge, which indicates that the challenge uses a custom winning criterion. \$\endgroup\$
    – Martin Ender
    Commented Jan 15, 2015 at 7:49
  • \$\begingroup\$ I think it would help if you said what associativity conventions your notation is using. \$\endgroup\$
    – xnor
    Commented Jan 15, 2015 at 8:01
  • \$\begingroup\$ The cycle as you've defined it isn't necessarily well defined, because a given expression can have multiple reductions available. \$\endgroup\$
    – Peter Taylor
    Commented Jan 15, 2015 at 8:09
  • \$\begingroup\$ @ThreeFx, you're mistaken. E.g. if x has a reduction to y then W f x -> W f y -> f y y or W f x -> f x x -> f x y -> f y y are different lengths. \$\endgroup\$
    – Peter Taylor
    Commented Jan 15, 2015 at 9:26
  • 4
    \$\begingroup\$ Now the tricky thing is that someone can't claim a score just by posting a cycle; they need a proof that there is no shorter reduction, which might be computationally difficult. \$\endgroup\$
    – xnor
    Commented Jan 15, 2015 at 10:25

2 Answers 2

Reset to default
9
\$\begingroup\$

Cycle: \$f_{\omega^{\omega^{\omega^{\omega^\omega}}}}(65536)\$, combinators: 98

W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) (C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) (C (C (C (C (W B) (W B)) (W B))) (W B))))

This expression is similar to Y I, that has this reduction:

0:  Y I
1:  I (Y I)
2:  Y I

After the first reduction there were two possible reductions: I (Y I) -> Y I and I (Y I) -> I (I (Y I)). This is not a problem since the second will clearly take longer to finish.

We will replace the I with j, j does the same thing I does, but it needs n reductions. n is an arbitrarily large Church numeral that cannot be reduced without an argument.

j = C (C (S (C I W) (C (C (C I K))))) n
y = Y j      <- This is just to make it easier to read later.

To make sure that there is no reduction of y that takes less than n steps, most of the time there will be only one possible reduction.

Imagine we have an expression a b that can be reduced to c, we can change it to C (C a) b. This new expression cannot be reduced, but if we give it another argument it can:

C (C a) b d
C a d b
a b d
c d

This way we can lock an expression to be reduced later. This can be seen in j, it can only be reduced with an argument.

In these first reductions only the leftmost combinator can be reduced.

0:  Y (C (C (S (C I W) (C (C (C I K))))) n)
1:  C (C (S (C I W) (C (C (C I K))))) n y    <- From now on y can always be reduced,
2:  C (S (C I W) (C (C (C I K)))) y n           but as we have seen before this makes
3:  S (C I W) (C (C (C I K))) n y               the cycle longer, so we can imagine
4:  C I W n (C (C (C I K)) n) y                 it cannot be reduced.
5:  I n W (C (C (C I K)) n) y
6:  n W (C (C (C I K)) n) y

Now n received an argument, it can be reduced and it is the only possible reduction.

For now let's reduce n completely before reducing anything else.

?:  W (W (W (...(W (W  (C (C (C I K)) n)  ))...))) y
    ^  ^  ^  ^^^ ^  ^   there are n 'W's here

C (C (C I K)) n needs an argument and each W needs two, so the first W is the only reduction allowed.

?:  W (W (W (...(W (W (C (C (C I K)) n)))...))) y
?:  W (W (...(W (W (C (C (C I K)) n)))...)) y y
?:  W (...(W (W (C (C (C I K)) n)))...) y y y
?:  ...(W (W (C (C (C I K)) n)))... y y y y
    ...
?:  W (W (C (C (C I K)) n)) y ... y y y
?:  W (C (C (C I K)) n) y y ... y y y
?:  C (C (C I K)) n y y y ... y y y        <- Let's call this line L
                      ^ ^ ^^^ ^ ^ ^  there are n 'y's after the first 'y'

Now C (C (C I K)) n has an argument, the only way this can happen is if n has been fully reduced and there are no Ws left. Here we assume n has not been designed to avoid line L, when defining n later I will show how this can be done.

After reduction 6 we reduced n completely, this was not necessary, the only other thing we could reduce besides n was the Ws. It doesn't matter what order we reduce it, it will always eventually reach line L. When n is reduced it makes n copies of W, this can be done in many ways and maybe even in less than n reductions, but the Ws make n copies of y one by one, this takes n reductions independently of when it happens or if the Ws were copied efficiently. From line 6 to line L the reductions can be made in many possible orders, but it will take at least n reductions to make all the copies of y.

Continuing from line L:

>n  :   C (C (C I K)) n y y y ... y y y
>n+1:   C (C I K) y n y y ... y y y
>n+2:   C I K n y y y ... y y y
>n+3:   I n K y y y ... y y y
>n+4:   n K y y y ... y y y

The only thing we can do now is reduce the n and the Ks. For the same reason as before this also takes at least n reductions.

Each one of the n Ks deletes one of the (n+1) ys, resulting in just one y. Reducing n completely before reducing the Ks would look like this:

>n+5:       K (K (K (...(K (K y))...))) y y y ... y y
>n+6:       K (K (...(K (K y))...)) y y ... y y
>n+7:       K (...(K (K y))...) y ... y y
            ...
>2n-2:      K (K y) y y
>2n-1:      K y y
>2n  :      y

Here is one complete example of this with n = 3 = S B (W B), which should take more than 6 reductions:

^ represents the possible reductions and (^) represents the reduction that will be done. If there is more than one option, one of them will be chosen at random.

0:  Y (C (C (S (C I W) (C (C (C I K))))) (S B (W B)))
   (^)
1:  C (C (S (C I W) (C (C (C I K))))) (S B (W B)) y
   (^)
2:  C (S (C I W) (C (C (C I K)))) y (S B (W B))
   (^)
3:  S (C I W) (C (C (C I K))) (S B (W B)) y
   (^)
4:  C I W (S B (W B)) (C (C (C I K)) (S B (W B))) y
   (^)
5:  I (S B (W B)) W (C (C (C I K)) (S B (W B))) y
   (^)
6:  S B (W B) W (C (C (C I K)) (S B (W B))) y       <- beginning of the reduction of n
   (^)
7:  B W (W B W) (C (C (C I K)) (S B (W B))) y
    ^   (^)
8:  B W (B W W) (C (C (C I K)) (S B (W B))) y
   (^)
9:  W (B W W (C (C (C I K)) (S B (W B)))) y
   (^) ^
10: B W W (C (C (C I K)) (S B (W B))) y y           <- 1st copy of y
   (^)
11: W (W (C (C (C I K)) (S B (W B)))) y y           <- end of the reduction of n
   (^)
12: W (C (C (C I K)) (S B (W B))) y y y             <- 2nd copy of y
   (^)
13: C (C (C I K)) (S B (W B)) y y y y               <- 3rd copy of y
   (^)
14: C (C I K) y (S B (W B)) y y y
   (^)
15: C I K (S B (W B)) y y y y
   (^)
16: I (S B (W B)) K y y y y
   (^)
17: S B (W B) K y y y y                             <- beginning of the second reduction of n
   (^)
18: B K (W B K) y y y y
   (^)   ^
19: K (W B K y) y y y
    ^ (^)
20: K (B K K y) y y y
   (^) ^
21: B K K y y y                                     <- 1st y deleted
   (^)
22: K (K y) y y                                     <- end of the second reduction of n
   (^)
23: K y y                                           <- 2nd y deleted
   (^)
24: y                                               <- 3rd y deleted

We can see that indeed it took more than 6 reductions.

Y is not allowed in this challenge, but we can replace it with W (B (S I)) (W (B (S I))):

0:  W (B (S I)) (W (B (S I))) j
1:  B (S I) (W (B (S I))) (W (B (S I))) j
2:  S I (W (B (S I)) (W (B (S I)))) j        <- Here we don't reduce the W for the
3:  I j (W (B (S I)) (W (B (S I))) j)           same reason we don't reduce Y twice
4:  j (W (B (S I)) (W (B (S I))) j)             before the end of the cycle.
5:  W (B (S I)) (W (B (S I))) j

Now we just need to choose some n to put in the expression:

W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) n)

Using this strategy we can guarantee that for a number n this expression will need at least 2n reductions, but n has three restrictions:

  • n must need an argument to be reduced
  • n must have 80 combinators or less (so far we used 19 of the 99)
  • n must not avoid line L

n could be designed to avoid line L:

n = 1 = C B (B I)
C B (B I) W (C (C (C I K)) n) y
B W (B I) (C (C (C I K)) n) y
W (B I (C (C (C I K)) n)) y
B I (C (C (C I K)) n) y y
I (C (C (C I K)) n y) y

In the last line if we reduce the I it becomes line L, but we can also reduce C (C (C I K)) n y. The way we will define n avoids this because we will add 1 many times to a number that doesn't skip line L. It would have been harder to find a definition that does run into this problem, almost anything we can do is naturally forced to reach line L.

Let [a] be a function that represents \$f_a\$ in the fast-growing hierarchy. We will also need some other functions that will be implemented later, here are their definitions:

d1 f x       = x f x
d2 f g x     = x f g x
d3 f g h x   = x f g h x
d4 f g h i x = x f g h i x
...

By definition, applying [a] x times to x is equivalent to [a+1] x:

x [a] x = d1 [a] x = [a+1] x

Applying d1 to [a] increases a by 1, doing this x times gives:

x d1 [a] x = d2 d1 [a] x = [a+x] x = [a+w] x

Now that we can add \$\omega\$, we can do this x times:

x (d2 d1) [a] x = d2 (d2 d1) [a] x = [a+wx] x = [a+w^2] x

Here we have a pattern:

d1 [a] x              = [a+1  ] x
d2 d1 [a]             = [a+w  ] x
d2 (d2 d1) [a] x      = [a+w^2] x  <- we stopped here
d2 (d2 (d2 d1)) [a] x = [a+w^3] x
...
k  d2 d1 [a] x        = [a+w^k] x
d3 d2 d1 [a] x        = [a+w^w] x

And here another:

d1 [a] x                = [a+1] x
d2 d1 [a] x             = [a+w] x
d3 d2 d1 [a] x          = [a+w^w] x     <- we stopped here
d4 d3 d2 d1 [a] x       = [a+w^w^w] x
d5 d4 d3 d2 d1 [a] x    = [a+w^w^w^w] x
d6 d5 d4 d3 d2 d1 [a] x = [a+w^w^w^w^w] x

I won't prove these patterns are correct, it would take many lines and would be very repetitive, this is left as an exercise to the reader.

We will use that last function, with [a] = [0] = S B.

These are the definitions of the ds:

d1 =                                                                                      B W (C I)
d2 =                                                                             B (B W) (B C (C I))
d3 =                                                                B (B (B W)) (B (B C) (B C (C I)))
d4 =                                               B (B (B (B W))) (B (B (B C)) (B (B C) (B C (C I))))
d5 =                          B (B (B (B (B W)))) (B (B (B (B C))) (B (B (B C)) (B (B C) (B C (C I)))))
d6 = B (B (B (B (B (B W))))) (B (B (B (B (B C)))) (B (B (B (B C))) (B (B (B C)) (B (B C) (B C (C I))))))

Each function uses part of the previous, this can be used to reduce the number of combinators to this expression:

S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W) (C I) (S B) x

This expression is reducible, we can use the C (C a) b trick to solve this problem:

C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) x

The only thing missing is the input, we can use 13 combinators to reach some big number that cannot be reduced without an argument.

The largest number I found was 65536 using 12 combinators:

C (C (C (C (W B) (W B)) (W B))) (W B)

Putting everything together gives an expression with 98 combinators and a cycle of at least \$2 f_{\omega^{\omega^{\omega^{\omega^\omega}}}}(65536)\$ reductions.

W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) (C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) (C (C (C (C (W B) (W B)) (W B))) (W B))))
'-----------.-----------'                                     '----------------------------------------------------------------------------------------------------------------------.----------------------------------------------------------------------------------------------------------------------'  '-----------------.-----------------'
            Y                                                                                                                                                                   f_w^w^w^w^w                                                                                                                                    65536
                           '------------------------------------------------------------------------------------------------------------------------------------------------------------.------------------------------------------------------------------------------------------------------------------------------------------------------------'
                                                                                                                                                                                        j
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ ...How big is that number? \$\endgroup\$
    – thejonymyster
    Commented Oct 12, 2021 at 16:19
  • 2
    \$\begingroup\$ @thejonymyster Bigger than Graham's number and about the size of a Goodstein sequence starting with 10^10^19728 \$\endgroup\$
    – 2014MELO03
    Commented Oct 12, 2021 at 22:06
7
\$\begingroup\$

Gotta start with something

1:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

2:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

3:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

4:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

5:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

6:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

7:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

8:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

9:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

10:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

11:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

12:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

13:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

14:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

15:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

16:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

17:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

18:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

19:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

20:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

21:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

22:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

23:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

24:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

25:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

26:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

27:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

28:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

29:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

30:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

31:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.