Kombinator-Quines

Hintergrund

Sie haben gerade gelernt, was kombinatorische Logik ist. Fasziniert von den verschiedenen Kombinatoren verbringen Sie viel Zeit damit, sie kennenzulernen. Sie stolpern schließlich über diesen besonderen Ausdruck:

(S I I (S I I))

Sie bemerken, dass beim Versuch, es auf seine normale Form zu reduzieren, es nach drei Schritten auf sich selbst reduziert wird:

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

Sie sind entschlossen, andere Ausdrücke zu finden, die dieses Merkmal teilen, und sofort damit zu beginnen.

Regeln

Sie können eine beliebige Kombination der folgenden Kombinatoren verwenden:

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

Die Anwendung bleibt assoziativ, was bedeutet, dass dies (S K K)tatsächlich der Fall ist ((S K) K).
Eine Reduzierung ist minimal. Es gibt keine andere Reihenfolge von Reduktionsschritten, die weniger Schritte verwendet. Beispiel: Wenn xeine Reduzierung vorliegt y, ist die korrekte minimale Reduzierung von (W f x):
```
(W f x)
= (W f y) (1)
= f y y   (2)
```
und nicht
```
(W f x)
= f x x   (1)
= f y x   (2)
= f y y   (3) 
```
Es gelten Standardlücken.

Aufgabe

Wir definieren den Zyklus eines Ausdrucks als die minimale Anzahl von Reduktionen zwischen zwei gleichen Ausdrücken.

Ihre Aufgabe ist es, den Ausdruck mit der Anzahl der verwendeten Kombinatoren <100 zu finden, der den längsten Zyklus erzeugt.

Wertung

Ihre Punktzahl wird durch die Länge des Zyklus Ihres Ausdrucks bestimmt. Wenn der Ausdruck von zwei Personen den gleichen Zyklus hat, gewinnt die Antwort, die weniger Kombinatoren verwendet. Wenn beide die gleiche Anzahl von Kombinatoren verwenden, gewinnt die frühere Antwort.

Viel Glück und hab Spaß!

code-challenge quine busy-beaver ThreeFx
quelle

Atomic-Code-Golf würde für Ihren Tie Breaker passen, aber ich würde kein Tag für den Tie Breaker hinzufügen. Wenn kein geeignetes Tag vorhanden ist, lautet die Standardeinstellung Code-Challenge . Dies zeigt an, dass für die Challenge ein benutzerdefiniertes Gewinnkriterium verwendet wird.

Martin Ender

Ich denke, es wäre hilfreich, wenn Sie sagen würden, welche Assoziativitätskonventionen Ihre Notation verwendet.

xnor

Der Zyklus, wie Sie ihn definiert haben, ist nicht unbedingt gut definiert, da für einen bestimmten Ausdruck mehrere Reduzierungen verfügbar sein können.

Peter Taylor

@ThreeFx, du liegst falsch. ZB wenn xhat eine Reduktion auf ydann W f x -> W f y -> f y yoder W f x -> f x x -> f x y -> f y ysind unterschiedliche Längen.

Peter Taylor

Das Schwierige ist nun, dass jemand nicht einfach durch Posten eines Zyklus eine Punktzahl beanspruchen kann. Sie benötigen einen Beweis dafür, dass es keine kürzere Reduzierung gibt, was rechenintensiv sein könnte.

xnor

Antworten:

Ich muss mit etwas anfangen

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
quelle