Najmniejszy możliwy uniwersalny kombinator

Szukam najmniejszego możliwego uniwersalnego kombinatora , mierzonego liczbą abstrakcji i aplikacji wymaganych do określenia takiego kombinatora w rachunku lambda . Przykłady uniwersalnych kombinatorów obejmują:

rozmiar 23: λf.f (fS (KKKI)) K.
rozmiar 18: λf.f (fS (KK)) K.
rozmiar 14: λf.fKSK
rozmiar 12: λf.fS (λxyz.x)
rozmiar 11: λf.fSK

gdzie S = λxyz.xz (yz) o rozmiarze 6 i K = λxy.x o rozmiarze 2 są kombinatorami rachunku kombinatorycznego SK . Pierwsze 4 przykłady opisano w tym artykule .

Moje pytania to:

Czy istnieją uniwersalne kombinatory o mniejszych rozmiarach?
Jaki jest najmniejszy możliwy uniwersalny kombinator?

EDYCJA: Zobacz także /math//a/180263/76284 , który ma λazbc.bc(a(λy.c))(który miałby rozmiar 8 , pasujący do sumy rozmiarów podstawy SK). Czy ktoś wie, jak wyrazić S i K z tego kombinatora?

— użytkownik76284
źródło

Może to jest interesujące: wolframscience.com/nksonline/page-1123a-text?firstview=1

— Andrej Bauer

Jaka jest twoja definicja rozmiaru? Czy możesz napisać to jako funkcję?

— Joshua Herman

Ponieważ 6 + 2 = 8 <11, zastanawiam się, czy {S, K} jest najmniejszą podstawą kombinatorów mierzonych całkowitym rozmiarem?

— Noam Zeilberger,

Twoja ostatnia edycja brzmi raczej jak (częściowa) odpowiedź.

— Emil Jeřábek wspiera Monikę

Jak ściśle definiujesz „ kombinator ”? Czy musi mieć formę, w λx*.Ektórej nie Ezawiera abstrakcji?

— Peter Taylor

Odpowiedzi:

Należy zauważyć, że znalezienie kombinatorów z pewnymi właściwościami redukującymi jest zawsze trudne, a znalezienie najmniejszego takiego kombinatora może być łatwo nierozstrzygalne (z błahych powodów, ponieważ może być nierozstrzygalne, aby udowodnić, że pewne zastosowanie kombinacji nawet zatrzymuje się).

Istnieje kilka prostych otwartych pytań o podobnym smaku, np. Problemy # 4, # 6 i # 10 z listy otwartych problemów TLCA .

Należy zwrócić uwagę na to, że twój kombinator z pewnością musi mieć co najmniej 2 powiązane zmienne, z których jedna jest zduplikowana (podobnie jak każdy kompletny zestaw kombinacji) i jedna musi zostać skasowana. Wydaje mi się, że to dolna granica 4 (2 abstrakty i 2 pojawienia się zmiennej), która nie jest tak daleko od górnej granicy 11.

Edycja: komentarze i referencje Noama przesuwają dolną granicę do 5! Nie zdziwiłbym się, gdyby dowód wymagał również pojawienia się dodatkowej zmiennej, co zepchnęłoby nas do 6.

— cody
źródło

W rzeczywistości dwie zmienne nie są wystarczające ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), więc daje to nieco wyższą dolną granicę (rozmiar 5 = 3 abstrakcje i 2 aplikacje).

— Noam Zeilberger,

@NoamZeilberger w porządku, to fantastyczny wynik, którego nie byłem świadomy!

— cody

W przypadku pierwszego pytania uważam, że ten artykuł może pomóc grupie. Ma 6-bitowy rachunek kombinatoryczny, który jest również UTM. Ma też uniwersalny kombinator, który wydaje się mieć rozmiar 7 z jednym elementem, biorąc pod uwagę to, czego chcesz. Nazywają to Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

Nie jestem pewien, czy możesz powiedzieć lub udowodnić, że istnieje minimalny kombinator. Artykuł sugeruje, że musiałby być co najmniej mniej niż 6 bitów.

— Joshua Herman
źródło

Kombinator Zota jest faktycznie ostatnim wymienionym w OP: λx.xSK (współdzielony z jego językami nadrzędnymi, Iota i Jot), który ma długość 11. W „rachunku bitowym kombinatora” (Keraia) „6 bitów” to rozmiar UTM; i wygląda na to, że jest to po prostu kodowanie rachunku lambda, a nie rachunku kombinatorycznego (a zatem nie ma wbudowanego uniwersalnego kombinatora).

— 2012rcampion