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?
lo.logic
computability
lambda-calculus
universal-computation
combinatory-logic
użytkownik76284
źródło
źródło
λx*.Ektórej nieEzawiera abstrakcji?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.
źródło
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.
źródło