Quin Combinator

Latar Belakang

Anda baru saja belajar apa itu logika kombinasional . Penasaran dengan berbagai kombinator yang Anda habiskan cukup banyak waktu untuk mempelajarinya. Anda akhirnya menemukan ungkapan khusus ini:

(S I I (S I I))

Anda perhatikan bahwa ketika mencoba menguranginya ke bentuk normal, itu berkurang dengan sendirinya setelah tiga langkah:

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

Anda bertekad untuk menemukan ekspresi lain yang memiliki sifat ini dan mulai mengerjakannya segera.

Aturan

Anda dapat menggunakan kombinasi apa saja dari kombinator berikut:

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

Aplikasi dibiarkan asosiatif, yang artinya (S K K)sebenarnya ((S K) K).
Reduksi minimal, tidak ada urutan langkah reduksi lain yang menggunakan langkah lebih sedikit. Contoh: jika xmemiliki reduksi y, maka reduksi minimal yang benar (W f x)adalah:
```
(W f x)
= (W f y) (1)
= f y y   (2)
```
dan tidak
```
(W f x)
= f x x   (1)
= f y x   (2)
= f y y   (3) 
```
Celah standar berlaku.

Tugas

Kami mendefinisikan siklus ekspresi menjadi jumlah minimal pengurangan di antara dua ekspresi yang sama.

Tugas Anda adalah menemukan ekspresi, dengan jumlah kombinator yang digunakan <100, yang menghasilkan siklus terpanjang.

Mencetak gol

Skor Anda akan ditentukan oleh lamanya siklus ekspresi Anda. Jika ekspresi dua orang memiliki siklus yang sama, jawaban yang menggunakan lebih sedikit kombinator akan menang. Jika keduanya menggunakan jumlah combinator yang sama, jawaban sebelumnya menang.

Semoga berhasil dan selamat bersenang - senang!

code-challenge quine busy-beaver ThreeFx
sumber

atomic-golf-golf cocok untuk pemutus dasi Anda, tapi saya tidak akan menambahkan tag untuk pemutus dasi. Jika tidak ada tag yang sesuai, maka standarnya adalah tantangan kode , yang menunjukkan bahwa tantangan tersebut menggunakan kriteria pemenang kustom.

Martin Ender

Saya pikir itu akan membantu jika Anda mengatakan konvensi asosiasi apa yang digunakan oleh notasi Anda.

xnor

The siklus Anda telah menetapkan tidak didefinisikan tentu baik, karena ekspresi yang diberikan dapat memiliki beberapa pengurangan tersedia.

Peter Taylor

@ThreeFx, Anda salah. Misalnya jika xmemiliki pengurangan untuk yitu W f x -> W f y -> f y yatau W f x -> f x x -> f x y -> f y ypanjangnya berbeda.

Peter Taylor

Sekarang hal yang sulit adalah bahwa seseorang tidak dapat mengklaim skor hanya dengan memposting siklus; mereka membutuhkan bukti bahwa tidak ada pengurangan yang lebih pendek, yang mungkin sulit secara komputasi.

xnor

Jawaban:

Harus mulai dengan sesuatu

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

desir
sumber