Pytania oznaczone «lambda-calculus»

System formalny Kościoła używany w obliczeniach, językach programowania i teorii dowodów do reprezentowania skutecznych funkcji, programów i ich obliczeń oraz dowodów.

21
Czy wpisane obliczenia lambda wyrażają * wszystkie * algorytmy poniżej określonej złożoności?

Wiem, że złożoność większości odmian kalkulatorów lambda bez prymitywu kombinatora Y jest ograniczona, tzn. Można wyrazić tylko funkcje o ograniczonej złożoności, przy czym granica staje się większa wraz ze wzrostem ekspresyjności systemu typów. Pamiętam, że np. Rachunek konstrukcji może wyrażać co...

19
Rachunek Lambda dla funkcji odwracalnych (obliczalnych r-Turinga)

Interesuje mnie koncepcja „kompletności r-Turinga”, zdefiniowana przez Axelsena i Glück (2011) . System jest gotowy do r-Turinga, jeśli może obliczyć ten sam zestaw funkcji, co odwracalna maszyna Turinga, bez generowania żadnych „śmieciowych” danych. Jest to to samo, co możliwość obliczenia każdej...

18
Jaki jest sens konwersji

Myślę, że tego nie rozumiem, ale konwersja wygląda na mnie jako konwersja β , która nic nie robi, szczególny przypadek konwersji β, w której wynikiem jest tylko termin z abstrakcji lambda, ponieważ nie ma nic do zrobienia, rodzaj bezcelowej konwersji β .ηη\etaββ\betaββ\betaββ\beta Może więc...

18
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?

Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...