Timeline for Smallest possible universal combinator
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2023 at 15:02 | comment | added | John Tromp | There are 2 more minimal (26 bit) universal ones: λx λy λz. y z (x (λ_.z)) and x λy λz. y (λ_.z) (x z), although they require longer expressions for S and K. | |
| Dec 24, 2023 at 23:31 | comment | added | user76284 | And are there other universal terms of equal size, or is it unique? | |
| Dec 24, 2023 at 21:48 | comment | added | user76284 | Interesting. Do you have an idea of when it will be published? | |
| Dec 24, 2023 at 15:47 | comment | added | John Tromp | Our exhaustive search found all terms of fewer than 26 bits not to provide a basis, but the work is unpublished. | |
| Dec 23, 2023 at 22:20 | comment | added | user76284 | Thanks for your answer. Is there a proof that this is the smallest possible size? | |
| Dec 23, 2023 at 19:23 | history | answered | John Tromp | CC BY-SA 4.0 |