Na stronie Wikipedii dla Fixed Point Combinators jest napisany dość tajemniczy tekst
Kombinator Y jest przykładem tego, co powoduje, że rachunek Lambda jest niespójny. Dlatego należy to traktować podejrzliwie. Można jednak bezpiecznie rozważyć kombinator Y, gdy jest on zdefiniowany tylko w logice matematycznej.
Czy wdałem się w jakąś powieść szpiegowską? Co na świecie rozumie się przez stwierdzenia, że -kalkulus jest „niespójny” i że należy go „podejrzewać” ?
Odpowiedzi:
Jest inspirowany prawdziwymi wydarzeniami, ale sposób, w jaki zostało powiedziane, jest ledwo rozpoznawalny i „należy podejrzewać” to nonsens.
Spójność ma dokładne znaczenie logiczne: spójna teoria to taka, w której nie wszystkie dowody można udowodnić. W logice klasycznej, jest to równoznaczne z brakiem sprzeczności, czyli teoria jest sprzeczny wtedy i tylko wtedy, gdy znajduje się zdanietakie, że teoria dowodzi zarównoi jego negacja.A A ¬A
Co to oznacza w odniesieniu do rachunku lambda? Nic. Rachunek lambda to system przepisywania, a nie logiczna teoria.
Możliwe jest przeglądanie rachunku lambda w odniesieniu do logiki. Traktuj zmienne jako reprezentujące hipotezę w dowodzie, abstrakcje lambda jako dowody w ramach pewnej hipotezy (reprezentowanej przez zmienną), a zastosowanie jako zestaw warunkowego dowodu i dowodu hipotezy. Następnie reguła beta odpowiada uproszczeniu dowodu poprzez zastosowanie modus ponens , podstawowej zasady logiki.
Działa to jednak tylko wtedy, gdy dowód warunkowy jest połączony z dowodem słusznej hipotezy. Jeśli masz dowód warunkowy, który zakłada, że a także masz dowód , nie możesz łączyć ich razem. Jeśli chcesz, aby ta interpretacja rachunku lambda działała, musisz dodać ograniczenie, że tylko dowody właściwej hipotezy zostaną zastosowane do dowodów warunkowych. Nazywa się to systemem typów , a ograniczeniem jest reguła pisania, która mówi, że gdy przekazujesz argument do funkcji, typ argumentu musi być zgodny z typem parametru funkcji.n=3 n=2
Korespondencja Curry-Howard jest równoległy pomiędzy wpisywanych kamieni i systemów dowodu.
Wpisany rachunek różniczkujący, który ma kombinator punktów stałych, taki jak pozwala na zbudowanie dowolnego rodzaju wyrażenia (spróbuj ocenić ), więc jeśli weźmiesz logiczną interpretację przez korespondencję Curry-Howarda, otrzymasz niespójną teorię. Zobacz Czy kombinator Y jest sprzeczny z korespondencją Curry-Howarda? po więcej szczegółów.Y Y(λx.x)
Nie ma to znaczenia dla rachunku czystego lambda, tzn. Dla rachunku lambda bez typów.
W wielu kalkulacjach maszynowych nie można zdefiniować kombinatora punktów stałych. Te kalkulacje maszynowe są użyteczne ze względu na ich logiczną interpretację, ale nie stanowią podstawy dla kompletnego języka programowania Turinga. W niektórych kalkulacjach maszynowych możliwe jest zdefiniowanie kombinatora punktów stałych. Te kalkulatory są przydatne jako podstawa dla języka programowania pełnego Turinga, ale nie w odniesieniu do ich logicznej interpretacji.
Podsumowując:
źródło
true
ifalse
, a propozycje były rzeczy, które miały logiczną wartościową wyjście. (i były uważane jedynie propozycje na domenie rzeczy gdzie robi wyjście A wartość logiczną).Chciałbym dodać jeden do tego, co powiedział @Giles.
Korespondencji Curry-Howard sprawia równolegle między -terms (bardziej konkretnie, te typy z -terms) i systemy dowodu.λ λ
Na przykład ma typ (gdzie oznacza „funkcję od do ”), co odpowiada logicznej instrukcji . Funkcja ma typ , odpowiadający . Możemy przekonwertować dowolny typ rachunku lambda na logiczną tautologię poprzez, w pewnym sensie, „dopasowanie wzorca” funkcji.λx.λy.x a→(b→a) a→b a b a⟹(b⟹a) λx.λy.xy (a→b)→(a→b) (a⟹b)⟹(a⟹b)
Problem pojawia się, gdy weźmiemy pod uwagę kombinator Y, zdefiniowany jako . Problem powstaje, ponieważ oczekujemy, że kombinator Y, jako kombinator „punktu stałego”, będzie miał typ (ponieważ przenosi funkcję z typu na ten sam typ i znajduje ustalone- punkt dla tej funkcji, która ma ten typ). Przekształcenie tego w wyrażenie logiczne daje . To jest sprzeczność:λf.(λx.f(xx))(λx.f(xx)) (a→a)→a (a⟹a)⟹a
Zaakceptowanie systemu typu prowadzi do niespójności systemu typu. Oznacza to, że możemy(a→a)→a
źródło
fix
. Możesz po prostu stwierdzić, że dla każdego typu istnieje stała . To już da ci niespójny system, jeśli chodzi o CH, ponieważ oznaczałoby, że każdy typ jest zamieszkany przez . Możesz dodatkowo dodać -rules, aby wykonać , a to zamieniłoby, powiedzmy, STLC z naturals w system Turinga kompletny, ale nie musisz dodawać tych reguł obliczeniowych, a system nadal byłoby niespójne.