Jak dokładnie rachunek lambda uwzględnia intuicyjne pojęcie obliczalności?

Próbowałem owinąć głowę wokół tego, co, dlaczego i jak rachunek, ale nie jestem w stanie poradzić sobie z „dlaczego to działa”?$\lambda$

„Intuicyjnie” dostaję model obliczeniowy Turing Machines (TM). Ale ta abstrakcja wprawia mnie w zakłopotanie.$\lambda$

Załóżmy, że bazy danych nie istnieją - jak więc można „intuicyjnie” przekonać się o zdolności rachunku do uchwycenia tego pojęcia obliczalności. W jaki sposób posiadanie szeregu funkcji do wszystkiego i ich osobowość oznacza obliczalność? Czego tu brakuje? Przeczytałem na ten temat artykuł Alonzo Church, ale nadal jestem zdezorientowany i szukam bardziej „zamroczonego” zrozumienia tego samego.$\lambda$

$\lambda$

$\lambda$$\lambda$

Programujesz w nim! Spójrz na kodowanie kościoła . Możesz zobaczyć, jak właściwie można wykonać całą arytmetykę, co prawdopodobnie powinno cię przekonać, że jest niezwykle potężna. Lubię jednak patrzeć na operacje na listach. Możesz zdefiniować dowolną strukturę danych w kategoriach funkcji, która wykonuje na niej najważniejsze operacje.

Na przykład kodowanie listy to funkcja składania, która się na niej składa. Zauważ, że to nie jest kodowanie Kościoła, ale takie, które otrzymałem z typów i języków programowania Percie. Kodowanie par Kościoła nie daje nam rekurencji, musimy dodać to z powrotem do siebie za pomocą pewnego rodzaju kombinatora rekurencji.

tak więc lista przyjmuje dwa argumenty, funkcję wykonującą zwijanie i wartość początkową, którą w pewnym momencie podłącza się do zwijania.

cons x xs = lam f. lam a. f x (xs f a)
nil       = lam f. lam a. a

teraz możemy zdefiniować podsumowanie przy użyciu funkcji dodawania (patrz kodowania kościelne z góry)

sum xs = xs add 0

możemy zrobić więcej i zdefiniować funkcję mapy

consApply f x xs = cons (f x) xs
map f xs = xs (consApply f) nil

jeśli nadal nie jesteś przekonany, że tutaj trwają obliczenia i chcesz się upewnić, że możesz wykonać dowolne obliczenia, sprawdź kombinator punktów stałych . Czasem trochę boli mnie myślenie, ale nie jestem pewien, czy nazwałbym to intuicyjnie, ale jeśli ocenisz to ręcznie za pomocą kilku argumentów, zobaczysz, co się dzieje.