Liczby kościelne to kodowanie liczb naturalnych jako funkcji.
(\ f x → (f x)) -- church number 1
(\ f x → (f (f (f x)))) -- church number 3
(\ f x → (f (f (f (f x))))) -- church number 4Zgrabnie, możesz potęgować 2 liczby kościołów, po prostu je stosując. To znaczy, jeśli zastosujesz 4 do 2, otrzymasz numer kościoła 16, lub 2^4. Oczywiście jest to całkowicie niepraktyczne. Liczby kościelne wymagają liniowej ilości pamięci i są naprawdę, bardzo powolne. Obliczanie czegoś takiego 10^10- na które GHCI szybko odpowiada poprawnie - zajęłoby wieki i i tak nie mieściłoby się w pamięci komputera.
Ostatnio eksperymentowałem z optymalnymi oceniającymi λ. Podczas moich testów przypadkowo wpisałem na moim optymalnym kalkulatorze λ:
10 ^ 10 % 13Miało to być mnożenie, a nie potęgowanie. Zanim zdążyłem ruszyć palcami, aby przerwać wiecznie działający program w rozpaczy, odpowiedział na moją prośbę:
3
{ iterations: 11523, applications: 5748, used_memory: 27729 }
real 0m0.104s
user 0m0.086s
sys 0m0.019sZ migającym „alertem o błędzie” udałem się do Google i zweryfikowałem 10^10%13 == 3. Ale kalkulator λ nie miał znaleźć tego wyniku, ledwo może przechowywać 10 ^ 10. Zacząłem to podkreślać dla nauki. To natychmiast odpowiedział mi 20^20%13 == 3, 50^50%13 == 4, 60^60%3 == 0. Musiałem użyć zewnętrznych narzędzi, aby zweryfikować te wyniki, ponieważ sam Haskell nie był w stanie tego obliczyć (z powodu przepełnienia liczb całkowitych) (oczywiście jeśli używasz liczb całkowitych, a nie Intów!). Pchając go do granic, oto odpowiedź na 200^200%31:
5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }
real 0m4.025s
user 0m3.686s
sys 0m0.341sGdybyśmy mieli jedną kopię wszechświata dla każdego atomu we wszechświecie i mielibyśmy komputer dla każdego atomu, który mieliśmy w sumie, nie moglibyśmy przechowywać numeru kościoła 200^200. To skłoniło mnie do pytania, czy mój Mac jest naprawdę tak potężny. Być może optymalny oceniający był w stanie pominąć niepotrzebne gałęzie i uzyskać właściwą odpowiedź w taki sam sposób, jak Haskell robi z leniwą oceną. Aby to przetestować, skompilowałem program λ do Haskella:
data Term = F !(Term -> Term) | N !Double
instance Show Term where {
show (N x) = "(N "++(if fromIntegral (floor x) == x then show (floor x) else show x)++")";
show (F _) = "(λ...)"}
infixl 0 #
(F f) # x = f x
churchNum = F(\(N n)->F(\f->F(\x->if n<=0 then x else (f#(churchNum#(N(n-1))#f#x)))))
expMod = (F(\v0->(F(\v1->(F(\v2->((((((churchNum # v2) # (F(\v3->(F(\v4->(v3 # (F(\v5->((v4 # (F(\v6->(F(\v7->(v6 # ((v5 # v6) # v7))))))) # v5))))))))) # (F(\v3->(v3 # (F(\v4->(F(\v5->v5)))))))) # (F(\v3->((((churchNum # v1) # (churchNum # v0)) # ((((churchNum # v2) # (F(\v4->(F(\v5->(F(\v6->(v4 # (F(\v7->((v5 # v7) # v6))))))))))) # (F(\v4->v4))) # (F(\v4->(F(\v5->(v5 # v4))))))) # ((((churchNum # v2) # (F(\v4->(F(\v5->v4))))) # (F(\v4->v4))) # (F(\v4->v4))))))) # (F(\v3->(((F(\(N x)->F(\(N y)->N(x+y)))) # v3) # (N 1))))) # (N 0))))))))
main = print $ (expMod # N 5 # N 5 # N 4)To poprawnie wyprowadza 1( 5 ^ 5 % 4) - ale wrzuci cokolwiek powyżej, 10^10a utknie, eliminując hipotezę.
Optymalne oceniający użyłem jest 160-linie długie, unoptimized Program JavaScript, który nie zawierał jakichkolwiek wykładniczej modułu matematyki - i funkcja lambda-rachunek moduł Kiedyś była równie prosta:
(λab.(b(λcd.(c(λe.(d(λfg.(f(efg)))e))))(λc.(c(λde.e)))(λc.(a(b(λdef.(d(λg.(egf))))(λd.d)(λde.(ed)))(b(λde.d)(λd.d)(λd.d))))))Nie użyłem żadnego konkretnego modularnego algorytmu ani wzoru arytmetycznego. Jak więc optymalny oceniający jest w stanie dojść do właściwych odpowiedzi?
node test.js. Daj mi znać, jeśli masz jakieś pytania.