Czy można zdecydować równoważność w Systemie F (lub innym typowym rachunku λ)?

18

Wiem, że nie można zdecydować równoważności dla niepoprawnego rachunku lambda. Cytując Barendregt, HP Rachunek lambda: jego składnia i semantyka. Północna Holandia, Amsterdam (1984). :β

Jeśli A i B są rozłączne, niepuste zbiory terminów lambda, które są zamknięte na zasadzie równości, to A i B są rekurencyjnie nierozdzielne. Wynika z tego, że jeśli A jest nietrywialnym zbiorem terminów lambda zamkniętych na zasadzie równości, to A nie jest rekurencyjne. Nie możemy więc zdecydować o problemie „M = x?” dla konkretnego M. Wynika z tego, że Lambda nie ma modeli rekurencyjnych.

Jeśli mamy system normalizujący, taki jak System F, wówczas możemy zdecydować równoważność „z zewnątrz”, zmniejszając dwa podane warunki i porównując, czy ich normalne formy są takie same, czy nie. Czy jednak możemy to zrobić „od wewnątrz”? Czy istnieje kombinator System-F taki, że dla dwóch kombinacji i mamy jeśli i mają tę samą normalną postać, a przeciwnym razie? Czy można to zrobić przynajmniej dla niektórych ? Aby zbudować kombinator taki sposób, że jest prawdziwe iffβmiM.N.miM.N.=prawdziweM.N.miM.N.=fałszywyE M E M N N β MM.miM.miM.N.N.βM.? Jeśli nie to dlaczego?

Petr Pudlák
źródło

Odpowiedzi:

19

Nie, to niemożliwe. Rozważmy następujących dwóch mieszkańców typu .(ZAb)(ZAb)

M.=λfa.faN.=λfa.λza.faza

Są różne formy -Normal, ale nie można go odróżnić od lambda okresie, gdyż jest -expansion z i -expansion konserwy obserwacyjne równoważności w czystej wpisany lambda rachunku.N η M ηβN.ηM.η

Cody zapytał, co się stanie, jeśli zmienimy się przez równoważność. Odpowiedź jest nadal przecząca z powodu parametryczności. Rozważ następujące dwa terminy o typie :( α .η(α.αα)(α.αα)

M.=λfa:(α.αα).Λα.λx:α.fa[α.αα](Λβ.λy:β.y)[α]xN.=λfa:(α.αα).Λα.λx:α.fa[α]x

Są różne -normalne, -długie , ale są obserwacyjnie równoważne. W rzeczywistości wszystkie funkcje tego typu są równoważne, ponieważ to kodowanie typu jednostki, a więc wszystkie funkcje tego typu musi być równoważnie rozszerzony.η α .βη( α .α.αα(α.αα)(α.αα)

Neel Krishnaswami
źródło
2
Ok, to samo pytanie z -equivalence :)β,η
cody
11

Inna możliwa odpowiedź na całkowicie poprawną odpowiedź Neela: Załóżmy, że istnieje kombinator , dobrze napisany w systemie F, taki, który spełnia powyższy warunek. Typ to:Emimi

mi:α.ααbool

Okazuje się, że istnieje bezpłatne twierdzenie, które wyraża, że ​​taki termin jest koniecznie stały :

T., t,u,t,u:T., mi T. t u=mi T. t u

W szczególności jest funkcją zawsze prawdziwą lub funkcją stale fałszywą i nie może być prawdopodobnie „decydentem o równości”.mi

cody
źródło