Pytania otagowane jako 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.

2
Dziedziczna substytucja z hierarchią wszechświata
Czytałem o dziedzicznej zamianie na prosty rachunek Lambda i na logiczną strukturę z odrębnymi terminami i typami. Zastanawiam się, czy są jakieś przykłady dziedzicznej substytucji w systemie o typie zależnym i hierarchii wszechświata? tzn. gdzie True:Set0:Set1:Set2True:Set0:Set1:Set2 True : Set_0 : Set_1:Set_2 itd. Zastanawiam się w szczególności, jak ustalić miarę indukcyjną …
5
Reprezentowanie powiązanych zmiennych za pomocą funkcji od zastosowań do segregatorów
Problem reprezentowania zmiennych powiązanych w składni, a zwłaszcza podstawiania unikania przechwytywania, jest dobrze znany i ma wiele rozwiązań: zmienne nazwane z równoważnością alfa, wskaźniki de Bruijna, lokalna bezimienność, zbiory nominalne itp. Ale wydaje się, że istnieje inne dość oczywiste podejście, którego jednak nigdzie nie widziałem. Mianowicie, w podstawowej składni mamy …
3
Rachunek konstrukcji: skompresuj wyrażenie do jego najmniejszej postaci
Wiem, że Rachunek Konstrukcji jest silnie normalizujący, co oznacza, że ​​każde wyrażenie ma normalną wartość, która nie może być beta, a jeszcze bardziej zmniejszona eta. W rzeczywistości jest to najbardziej wydajne wyrażenie, które oblicza tę samą wartość, co oryginalne wyrażenie. Ale w niektórych przypadkach normalizacja może zredukować małe wyrażenie do …
1
Czy prawo wykluczenia środkowego implikuje aksjomat K w teorii typów wewnętrznych Intela Martina-Löfa?
Zastanawiam się więc, czy Prawo Wykluczonego Środka (LEM) implikuje tak zwany Axiom K w Intranice Teorii Typów Martina-Löfa. Aksjomat K stwierdza, że W rzeczywistości próbowałem udowodnić bardziej ogólne stwierdzenie, że ale po zredukowaniu do przez indukcję równości utknąłem w pierwszym problemie. Próbowałem też postępować w sprzeczności, ale wydaje się, że …
1
Rozległość modeli rachunku lambda
Tłumaczę książkę na temat LISP i oczywiście dotyka ona niektórych elementów rachunku. Zatem wzmiankowane jest pojęcie ekstensywności wraz z niektórymi modelami λ- rachunku, a mianowicie: P ω i D ∞ (tak, z nieskończonością u góry). I mówi się, że P ω jest ekstensjonalny podczas D ∞ nie jest.λλ\lambdaλλ\lambdaP.ωPω\mathcal{P}_\omegare∞D∞D^\inftyPωPω\mathcal{P}_\omegaD∞D∞D^\infty Ale ... …
6
Jaki jest sens nazywania
Jaka jest różnica nazywania calculus algebrą zamiast rachunku różniczkowego? Podnoszę to pytanie, ponieważ gdzieś przeczytałem wiersz „ λ- rachunek nie jest rachunkiem, ale algebrą” (iirc, przypisane Danie Scott). O co chodzi? Dzięki.λλ\lambdaλλ\lambda
3
Równoważne sformułowanie teorii złożoności w rachunku Lambda?
W teorii złożoności definicja złożoności czasu i przestrzeni odnosi się do uniwersalnej maszyny Turinga: odpowiednio. liczba kroków przed zatrzymaniem i liczba dotkniętych komórek na taśmie. Biorąc pod uwagę tezę Kościoła-Turinga, powinno być możliwe zdefiniowanie złożoności również pod względem rachunku lambda. Moje intuicyjne założenie jest takie, że złożoność czasu może być …
1
Algorytmy inwersji programów dla programów wyższego rzędu
Termin inwersja programu ma wiele odcieni znaczenia, ale prawdopodobnie zaczął się od pracy J. McCarthy'ego z 1956 r. Inwersja funkcji zdefiniowanych przez maszyny Turinga w kontekście sztucznej inteligencji. Do tej pory odkryto wiele połączeń między inwersją programu a innymi polami, np. Programowanie odwracalne (fizyczne i logiczne), częściowa ocena, weryfikacja, programowanie …
1
Niekompletna podstawa kombinacji
Jest to inspirowane tym pytaniem. Niech będzie zbiorem wszystkich kombinacji, które mają tylko dwie powiązane zmienne. Czy kombinatorycznie kompletny?C.dodo\mathcal{C}dodo\mathcal{C} Uważam, że odpowiedź jest przecząca, jednak nie udało mi się znaleźć odniesienia do tego. Byłbym również zainteresowany referencjami na dowody kombinatorycznej niekompletności zestawów kombinatorów (rozumiem, dlaczego zestaw składający się z kombinatorów …
1
Czy `sort 'można pisać na elementarnej logice afinicznej?
Następujący termin λ, tutaj w formie normalnej: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Implementuje algorytm sortowania dla list zakodowanych w kościele. Oznacza to, że wynik: sort (λ c n . (c 3 (c 1 (c 2 n)))) β→ (λ c n . (c 1 (c 2 (c 3 n)))) Podobnie, sort_below …
1
Jak kodujesz abstrakcyjny algorytm Lampinga za pomocą kombinacji interakcji?
Kombinatory interakcji były wcześniej proponowane jako cel kompilacji dla rachunku λ. Ten papier implementuje pełny rachunek λ. Wiadomo również, że możliwe jest zoptymalizowanie kodowania sieci interakcji rachunku λ dla podzbioru terminów λ, który jest typowy dla EAL. W tym artykule zaimplementowano ten podzbiór rachunku λ, tłumacząc wyrażenia λ typu EAL …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.