Combinator quines

9

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!

ThreeFx

Posted 2015-01-15T06:52:34.563

Reputation: 1 435

[tag: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 [tag:code-challenge], which indicates that the challenge uses a custom winning criterion. – Martin Ender – 2015-01-15T07:49:58.483

I think it would help if you said what associativity conventions your notation is using. – xnor – 2015-01-15T08:01:42.573

The cycle as you've defined it isn't necessarily well defined, because a given expression can have multiple reductions available. – Peter Taylor – 2015-01-15T08:09:46.953

@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. – Peter Taylor – 2015-01-15T09:26:14.860

@PeterTaylor In this case you would pick the first reduction, since it uses fewer steps. I tried to capture it in the wording "[..] the minimal number of reductions [..]". If you have an suggestion how to clarify it further, I would happily listen to it. I will also add an example to clarify the meaning. – ThreeFx – 2015-01-15T09:32:32.980

4Now 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. – xnor – 2015-01-15T10:25:25.023

@xnor This is indeed an issue, but I have faith in the participants to not intentionally abuse this fact and also in the community which judges the solutions that any "wrong" answers will be identified. – ThreeFx – 2015-01-15T11:52:12.750

So I was generating random expressions of length 100 for a while now and can't find a cycle longer that 31. Can it be the maximum? – swish – 2015-01-16T03:14:17.417

@swish I doubt that 31 is anywhere near the maximum. This challenge is pretty close to busy beaver territory, and I strongly suspect that the maximum answer is astronomically huge. The challenges would be (i) proving that the expression does indeed eventually reduce to itself, and (ii) showing that the proposed reduction scheme is indeed the minimal one. These are both, in general, hard problems.

– Nathaniel – 2016-08-27T06:56:30.877

Is "length" measured in characters? If so, does it include spaces? If so, are spaces compulsory, or can I write (S I I (S I I) as (SII(SII))? Or is length measured in number of base combinators instead? – Nathaniel – 2016-08-27T07:00:11.457

@Nathaniel "Fewer combinators", see scoring. – ThreeFx – 2016-08-27T12:07:10.737

@ThreeFx the scoring section specifies fewer combinators as a tie breaker. I'm asking about the task section, where it specifies length < 100. Do I take it from your comment that this means less that up to 99 combinators is OK, even if spaces and parentheses make the actual string longer than 100? – Nathaniel – 2016-08-27T16:42:52.790

@Nathaniel It's combinators as well, I'll edit that. – ThreeFx – 2016-08-27T16:43:35.367

Answers

7

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))

swish

Posted 2015-01-15T06:52:34.563

Reputation: 7 484

Asked: 2015-01-15T06:52:34.563

Viewed: 359 times

Active: 2017-01-04T14:17:16.220