Ocena rachunku lambda z udziałem cyfr kościelnych

10

Rozumiem, że liczba kościelna wygląda jak (... n razy ...) . Oznacza to nie więcej, niż „funkcja stosowanych razy do funkcji ”. λ s . λ z . s sdonλs.λz.ss n zszsnz

Możliwa definicja funkcji jest następująca: . Patrząc na ciało, rozumiem logikę tej funkcji. Jednak, kiedy zaczynam oceniać, utknąłem. Zilustruję to przykładem:t i m e s = λ m . λ n . λ s . mtjammistimes=λm.λn.λs.m(ns)

(λm.λn.λs.m(ns))(λs.λz.ssz)(λs.λz.sssz)λs.(λs.λz.ssz)((λs.λz.sssz)s))λs.(λs.λz.ssz)(λz.sssz)λs.λz.(λz.sssz)(λz.sssz)z

Teraz w tej sytuacji, jeśli najpierw zastosuję (λz.sssz)z , osiągnę pożądany rezultat. Jeśli jednak najpierw zastosuję (λz.sssz)(λz.sssz) , jak powinienem, ponieważ aplikacja jest skojarzona z lewej strony, otrzymuję zły wynik:

λs.λz.(λz.sssz)(λz.sssz)zλs.λz.(sss(λz.sssz))z

Nie mogę tego dłużej zmniejszać. Co ja robię źle? Wynik powinien być λs.λz.ssssssz

codd
źródło
Liczby kościelne w początkowej kadencji są nieprawidłowe. 2 jest reprezentowane przez , a nie . λ s . λ z . s s zλs.λz.s(sz)λs.λz.ssz
Uday Reddy,

Odpowiedzi:

7

Myślę, że twoja redukcja jest prawidłowa (chociaż tylko ją spojrzałem). Na koniec nie możesz zastosować do , to nigdy nie pojawia się w tym terminie. to , nie . Funkcje w rachunku lambda przyjmują jeden argument; są one efektywnie curry : funkcja dwuargumentowa jest implementowana jako funkcja jednoargumentowa, która przyjmuje pierwszy argument i zwraca nową funkcję jednoargumentową, która przyjmuje drugi argument i zwraca wynik.oo λ oo . f f z λ z . ( f f ) z λ z . f ( f z )(λz.sssz)zλz.fafazλz.(fafa)zλz.fa(faz)

Popełniłeś ten sam błąd podczas definiowania cyfr Kościoła. Cyfra Kościoła dla opiera się na skomponowaniu funkcji razy. „Funkcja zastosowane razy do funkcji ” . Co napisałeś jest funkcja zastosowane razy do funkcji i wreszcie do , co nie wydaje mi się użytecznym okresie.n s n z λ s . λ z . s ( s ( snnsnzs n - 1 s zλs.λz.s(s(sz)))sn-1sz

2)×3) jest zatem . Pozwolę ci sprawdzić, czy to redukuje do .(λmns.m(ns))(λsz.s(sz))(λsz.s(s(sz)))λsz.s(s(s(s(s(sz)))))

Gilles „SO- przestań być zły”
źródło
Jeśli chodzi o akapit, masz rację i wiedziałem o tym. Po prostu uderzyło mnie, że zastosowanie odpowiednio asocjatywnego skutkuje właściwym rezultatem. Co do drugiego akapitu: masz rację. Nieużywanie nawiasów klamrowych było dla mnie błędne, ponownie ze względu na lewe skojarzenie aplikacji. Znowu zredukuję to wszystko i zobaczę, czy mój brak aparatu nie spowodował mojego błędu!
codd
Tak się stało. Zauważasz, że moja notacja sugerowała niewłaściwą kolejność aplikacji rozwiązała problem! Akceptując twoją odpowiedź.
codd