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$

— Doktorat
źródło

Czy masz ten sam problem z przepisywaniem systemów i gramatyki? W rachunku lambda podstawowe operacje są dość proste: abstrakcja funkcji, zastosowanie funkcji przez podstawienie, a obliczenie jest normalizacją beta. Innymi słowy, nie widzę problemu z tym, że jest to rozsądny model obliczeniowy.

— Kaveh

Nie widziałem, aby ktokolwiek wątpił, że funkcje definiowane przez rachunek lambda są obliczalne. Historycznie pytanie dotyczyło tego, czy są to jedyne intuicyjnie obliczalne funkcje, co jest zupełnie inną kwestią niż to, co wydaje się zadawać.

— Kaveh

Jedną z rzeczy, które mi się przydały, była książka Raymonda M. Smullyana „Szyderczy drozda”, która zastępuje funkcje ptakami w magicznym lesie (i jest to dobra lektura)

— dspyz

Książka Smullyansa dotyczy logiki kombinatorycznej

— Trismegistos

Odpowiedzi:

$\lambda$

$\lambda$ $\lambda$

— Andrej Bauer
źródło

Jeśli firewalking jest tak zabawne, jak mówisz, to musi spróbować.

— Radu GRIGore,

Andrej, znasz jakieś referencje? Godel nie zaakceptował modelu Chrucha jako przechwytującego wszystkie funkcje komutowalne, ale nie pamiętam, aby widziałem, że skrytykował model znacznie dalej. Jego krytyka modelu rachunku lambada Kościoła była na równi z jego krytyką własnych ogólnych funkcji rekurencyjnych Godela-Herbranda, o ile mi wiadomo.

— Kaveh

Myślę, że chcesz K. Godela: „Kilka uwag na temat wyników nierozstrzygalności”, In Solomon Feferman, John Dawson i Stephen Kleene (red.), Kurt Gödel: Collected Works obj. Ii. Oxford University Press. 305--306 (1972). Zobacz books.google.si/…

— Andrej Bauer,

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.

— Jake
źródło