Funkcje, które wpisały rachunek lambda, nie mogą być obliczane

12

Chciałbym tylko poznać kilka przykładów funkcji, które można obliczyć za pomocą niepisanego rachunku lambda, ale nie za pomocą wpisanego rachunku lambda.

Jako że jestem początkującym, doceniłbym powtórzenie podstawowych informacji.

Dzięki.

Edycja: za pomocą kalkulatora lambda, miałem zamiar wiedzieć o systemie F i rachunku lambda po prostu. Przez funkcję rozumiem dowolną funkcję obliczalną Turinga.

pl.programming-languages type-theory lambda-calculus computable-analysis Timothy Zacchari
źródło

Istnieje wiele dyscyplin pisania dla

calculi, a odpowiedź na twoje zapytanie zależy częściowo od tego, jaki wybór dyscypliny pisania masz na myśli. Zależy to również od tego, co rozumiesz przez funkcję. Jednym z przykładów różnicy byłoby to, że dyscypliny pisania, takie jak System F, mogą pisać tylko programy normalizujące, podczas gdy niepoprawny rachunek

zawiera terminy nienormalizujące.

λ

$\lambda$

λ

$\lambda$

Martin Berger,

Myślałem o Systemie F i prostym typie rachunku lambda. Przez funkcję rozumiem funkcję obliczalną Turinga.

Timothy Zacchari,

15

Dobry przykład podaje Godelization: w rachunku lambda jedyne, co możesz zrobić z funkcją, to zastosować ją. W rezultacie nie ma możliwości napisania zamkniętej funkcji typu , która pobiera argument funkcji i zwraca dla niego kod Godela. $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$

Dodanie tego jako aksjomatu do arytmetyki Heytinga jest zwykle nazywane „konstruktywną tezą Kościoła” i jest silnie antyklasycznym aksjomatem. Mianowicie, spójne jest dodawanie go do HA, ale nie do arytmetyki Peano! (Zasadniczo jest to klasyczny fakt, że każda maszyna Turinga zatrzymuje się lub nie, i nie ma żadnej obliczalnej funkcji, która byłaby tego świadkiem.)

Neel Krishnaswami
źródło

Nie rozumiem, w jaki sposób jest to spójne z teorią ekstensywną: weź f i g równe, ale z różnymi implementacjami, a zatem różnymi kodami boskimi. Czy twoja funkcja zwraca ten sam numer dla f i g?

cody

3

To nie jest spójne z ekstensywnością! Jednak w HA

i

są logicznymi łącznikami, a nie funkcjami / rekordami. Muszą więc być wykonalni, ale ich realizatorzy nie muszą być ekstrawaganccy. Andrej Bauer jest ekspertem w tej dziedzinie, więc jeśli zadasz pytanie, na pewno otrzymasz dobrą odpowiedź.

\forall

$\forall$

\exists

$\exists$

Neel Krishnaswami,

11

Najprostszą odpowiedź daje fakt, że typowane lambda odpowiadają logice (po prostu typowany rachunek lambda -> logika predykatów; system f -> logika drugiego rzędu) i logika spójna nie może udowodnić swojej spójności.

Powiedzmy, że masz zapisane liczby naturalne (lub kodowanie liczb naturalnych w kościele) w zapisanym rachunku lambda. Możliwe jest wykonanie numeracji Gödla, która przypisuje każdy termin w systemie F unikatowej liczbie naturalnej. Następnie istnieje funkcja która przenosi dowolną liczbę naturalną (która odpowiada dobrze wpisanemu terminowi w Systemie F) na inną liczbę naturalną (która odpowiada normalnej formie tego dobrze wpisanego terminu w Systemie F) i robi coś innego dla dowolna liczba naturalna, która nie odpowiada dobrze wpisanemu terminowi w Systemie F (powiedzmy, zwraca zero). Funkcja jest obliczalna, więc można ją obliczyć na podstawie niepisanego rachunku lambda, ale nie na podstawie wypisanego rachunku lambda (ponieważ ten ostatni byłby dowodem spójności logiki drugiego rzędu w $f$ $f$ logika drugiego rzędu, co oznaczałoby, że logika drugiego rzędu jest niespójna).

Zastrzeżenie 1: Jeśli logika drugiego rzędu jest niespójna, może być możliwe napisanie w Systemie F ... i / lub może nie być możliwe zapisanie w nietypowym rachunku lambda - możesz coś napisać, ale może nie zawsze zakończ, co jest kryterium „obliczalnego”. $f$ $f$

Zastrzeżenie 2: Czasami przez „prosty typ rachunku lambda” ludzie mają na myśli „prosty typ rachunku lambda z operatorem punktu stałego lub funkcjami rekurencyjnymi”. Byłby to mniej więcej PCF , który może obliczyć dowolną funkcję obliczeniową, podobnie jak niepisany rachunek lambda.

Rob Simmons
źródło

10

W Untyped -calculus posseses ogólnie rekursji w postaci combinator. Po prostu wpisany -calculus nie. Zatem dowolna funkcja wymagająca ogólnej rekurencji jest kandydatem, na przykład funkcja Ackermanna. (Pomijam kilka szczegółów na temat tego, jak dokładnie reprezentujemy liczby naturalne w każdym systemie, ale zasadniczo wystarczy każde rozsądne podejście). $\lambda$ $Y$ $\lambda$

Oczywiście zawsze możesz rozszerzyć prosty calculus, aby dopasować moc , ale wtedy zmieniasz reguły gry. $\lambda$ $Y$

Andrej Bauer
źródło

Z jakiegoś powodu miałem w głowie, że możesz zrobić Ackermann w Systemie F ...

Rob Simmons

@Rob, jak rozumiem, Andrej nie twierdzi, że tak nie jest.

Kaveh

1

λ

$\lambda$

λ

$\lambda$

Och, racja, byłem po prostu głupi. (Ponieważ pytanie było dość dwuznaczne między mówieniem o Systemie F a mówieniem o STLC, wybrałem silniejszy system i zapomniałem o prostszym pytaniu.)

Rob Simmons

λ

$\lambda$

λ m . m (λ f n . n f (f \underline{1})) s u c

$\lambda m.m(\lambda f n.n f(f \underline{1}))~\mathsf{suc}$

(((((f \to e) \to f \to e) \to h) \to ((((f \to e) \to f \to e) \to h)

$(((((f \to e) \to f \to e) \to h) \to ((((f \to e) \to f \to e) \to h)$

\to h \to g) \to g) \to (((b \to c) \to a \to b) \to (b \to c) \to a \to c) \to d) \to d

$\to h \to g) \to g) \to (((b \to c) \to a \to b) \to (b \to c) \to a \to c) \to d) \to d$

Y

$Y$

6

$\mathtt{a}^*$

Sam Tobin-Hochstadt
źródło

5

(p \to p) \to p \to p

$(p \to p) \to p \to p$

p

$p$

2

$\lambda$

@Marting: Dzięki! Mieszkam teraz w Niemczech, więc jest to miła dodatkowa zachęta do ćwiczenia mojego niemieckiego. :)

Neel Krishnaswami,

4

Jedną z wizji granic silnie normalizujących się kamieni, które lubię, jest kąt obliczalności. W silnie znormalizowanym rachunku różniczkowym, takim jak rachunek prosty lambda, System F lub Rachunek konstrukcji, masz dowód, że wszystkie warunki w końcu się kończą.

Jeśli ten dowód jest konstruktywny, otrzymujesz stały algorytm do oceny wszystkich terminów z gwarantowaną górną granicą czasu obliczeń. Możesz też przestudiować (niekoniecznie konstruktywny) dowód i wyodrębnić z niego górną granicę - co prawdopodobnie będzie ogromne , ponieważ rachunek różniczkowy jest ekspresyjny.

Granice te dają „naturalne” przykłady funkcji, których nie można wpisać w tym ustalonym rachunku lambda: wszystkie funkcje arytmetyczne, które są asymptotycznie lepsze od tej granicy.

Jeśli dobrze pamiętam, terminy pisane w po prostu wpisany lambda-rachunek może być oceniany w wieżach wykładniczy: O(2^(2^(...(2^n)..); funkcja rosnąca szybciej niż wszystkie takie wieże nie będzie wyrażana w tym rachunku. System F odpowiada intuicyjnej logice drugiego rzędu, więc moc obliczeniowa jest po prostu ogromna. Aby wykorzystać siłę obliczeniową jeszcze mocniejszych teorii, zwykle rozumujemy w kategoriach teorii mnogości i teorii modeli (np. Jakie porządki można zbudować) zamiast teorii obliczalności.

gasche
źródło

0

$\Delta = \lambda x. x x$ $\Delta \Delta \to_\beta ~\Delta \Delta$ $\Delta$ $A$ $A = A \to A$

Charles
źródło

λ

$\lambda$

A

$A$

A \equiv A \to A

$A\equiv A \to A$

Tak, masz rację, ale pomyślałem (może się mylę), że nie było możliwe posiadanie takiego typu w prostym typie rachunku lambda lub w Systemie F, które oba są silnie normalizujące.

Charles

Δ Δ

$\Delta\Delta$

Δ Δ

$\Delta\Delta$

@Kaveh Dlaczego posiadające typ Ataki sposób, że A \ident A \rightarrow Anie dziwne? Brzmi dla mnie absurdalnie, co przeoczam?

Martijn

Prawdopodobnie myślisz klasycznie o zestawach i przestrzeniach funkcyjnych nad nimi. Pomyśl np. O skończonych ciągach binarnych i funkcjach obliczeniowych nad nimi.

Kaveh

Funkcje, które wpisały rachunek lambda, nie mogą być obliczane

Odpowiedzi: