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.

7
Jaki jest wkład rachunku lambda w dziedzinę teorii obliczeń?
Właśnie czytam rachunek lambda, żeby go „poznać”. Widzę to jako alternatywną formę obliczeń w przeciwieństwie do maszyny Turinga. Jest to interesujący sposób robienia rzeczy z funkcjami / redukcjami (z grubsza mówiąc). Niektóre pytania wciąż mnie dręczą: Jaki jest sens rachunku lambda? Po co przechodzić przez te wszystkie funkcje / ograniczenia? …
2
Teoria wykonalności: różnica mocy między rachunkiem lambda a maszynami Turinga
Mam trzy powiązane pytania, które są zaznaczone punktorami poniżej (nie, nie można ich podzielić, jeśli się zastanawiasz). Andrej Bauer napisał tutaj , że niektóre funkcje można realizować za pomocą maszyny Turinga, ale nie za pomocą rachunku lambda. Kluczowym krokiem jego rozumowania jest: Jeśli jednak użyjemy rachunku lambda, wówczas [program] c …
3
Wyjaśnienie klas P i NP za pomocą rachunku lambda
We wstępie i wyjaśnieniach klasy złożoności P i NP często podawane przez maszynę Turinga. Jednym z modeli obliczeń jest rachunek lambda. Rozumiem, że wszystkie modele obliczeń są równoważne (i jeśli możemy wprowadzić coś w kategoriach maszyny Turinga, możemy wprowadzić to w kategoriach dowolnego modelu obliczeń), ale nigdy nie widziałem wyjaśnienia …
4
Czy istnieje niepełny model Turinga, którego problem zatrzymania jest nierozstrzygalny?
Nie mogę wymyślić żadnego takiego modelu, może jakiejś formy wypisanego rachunku lambda? jakiś elementarny automat komórkowy? To prawie obaliłoby „zasadę równoważności obliczeniowej” Wolframa: Prawie wszystkie procesy, które nie są oczywiście proste, można postrzegać jako obliczenia o podobnym stopniu zaawansowania
2
Jaki był pierwotny zamiar stworzenia rachunku Lambda?
Czytałem, że początkowo Kościół zaproponował -calculus jako część swoich postulatów z logiki (co jest gęstym odczytem). Ale Kleene udowodnił, że jego „system” jest niespójny, po czym Church wyodrębnił odpowiednie rzeczy do swojej pracy nad „skutecznym obliczeniem” i porzucił wcześniejsze prace nad logiką.λλ\lambda Tak jak ja rozumiem, -system i jego oznaczenia …
3
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 najwyżej podwójnie wykładniczą złożoność. Moje pytanie dotyczy tego, czy …
2
Jak zdobyć Rachunek Konstrukcji z innych punktów w Kostce Lambda?
CoC jest zwieńczeniem wszystkich trzech wymiarów Lambda Cube. To wcale nie jest dla mnie oczywiste. Wydaje mi się, że rozumiem poszczególne wymiary, a połączenie dowolnych dwóch wydaje się skutkować względnie prostym zjednoczeniem (może czegoś mi brakuje?). Ale kiedy patrzę na CoC, zamiast wyglądać jak połączenie wszystkich trzech, wygląda to zupełnie …
2
Czy istnieje typowany rachunek lambda, który jest spójny i kompletny Turinga?
Czy istnieje typowany rachunek lambda, w którym odpowiednia logika w korespondencji Curry-Howarda jest spójna i gdzie istnieją możliwe do wpisania wyrażenia lambda dla każdej funkcji obliczeniowej? Jest to wprawdzie pytanie nieprecyzyjne, pozbawione precyzyjnej definicji „typowanego rachunku lambda”. Zastanawiam się, czy istnieją (a) znane przykłady tego, lub (b) znane dowody niemożności …
1
Stochastyczne obliczenia lambda Scotta
Ostatnio Dana Scott zaproponowała stochastyczny rachunek lambda, próbę wprowadzenia elementów probabilistycznych do (nietypowego) rachunku lambda w oparciu o semantykę zwaną modelem grafowym. Jego slajdy można znaleźć na przykład w Internecie , a jego artykuł w Journal of Applied Logic , t. 12 (2014). Jednak po szybkim przeszukaniu Internetu znalazłem podobne …
1
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 funkcji, która jest (a) obliczalna i (b) iniekcyjna. Chciałbym …
3
podświetlany i polaryzujący typy Pi
W ostatnim wątku na liście mailingowej Agdy pojawiło się pytanie o prawa ηη\eta , w których Peter Hancock wypowiedział się prowokująco . Rozumiem, że prawa ηη\eta mają typy negatywne, tj. łączniki, których zasady wprowadzania są odwracalne. Aby wyłączyć ηη\eta dla funkcji, Hank sugeruje użycie niestandardowego eliminatora, funsplit , zamiast zwykłej …
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.