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 dla czegoś w tej dziedzinie.

Edycja: @cody podaje dokładną wersję tego pytania w swojej odpowiedzi poniżej: czy istnieje logiczny system czystego typu (LPTS), który jest spójny i Turinga kompletny (w sensie zdefiniowanym poniżej)?

W porządku, poddam się temu: ogólnie dla danego systemu typów , prawda jest następująca:$T$

Jeśli wszystkie dobrze wpisane terminy w rachunku normalizują się, wówczas T jest spójne, gdy jest postrzegane jako logika.$T$$T$

Dowodem na ogół prowadzi się przy założeniu, że trzeba termin b Ś U r d typu F danej ł s e , poprzez redukcję z zastrzeżeniem uzyskania postaci normalnej, a następnie przebiega przez indukcję o strukturze takiej perspektywie się sprzeczność.$\mathrm{absurd}$$\mathrm{False}$

Naturalne jest zastanawianie się, czy rozmowa się utrzymuje, tj

Dla dowolnego systemu typu , jeśli T jest logicznie spójny , to każdy dobrze wpisany termin w T jest normalizujący.$T$$T$$T$

Problem polega na tym, że nie ma tak naprawdę najbardziej ogólnego pojęcia „systemu typów”, a tym bardziej nie jest zgodna co do znaczenia logicznej spójności dla takich systemów. Możemy jednak empirycznie to zweryfikować

W przypadku większości znanych systemów typu, które mają logiczną interpretację, odwrotność rzeczywiście się sprawdza.

W jaki sposób łączy się to z Turing Completeness? Cóż, po pierwsze, jeśli sprawdzanie typu jest rozstrzygalne , to argument Andreja pokazuje, że jedno z poniższych musi być spełnione :

1. Zestaw wszystkich dobrze napisanych programów nie jest Turing Complete.
2. Istnieje nie kończący się dobrze napisany program.

Sugeruje to, że:

Systemy typów, które mają logiczną interpretację i są spójne i są rekurencyjnie wyliczalne, nie są Turing Complete.

Podanie faktycznego twierdzenia zamiast sugestii wymaga doprecyzowania matematycznego pojęcia systemów typów i interpretacji logicznych.

Teraz przychodzą mi na myśl dwie uwagi:

1. Istnieje nierozstrzygalny system typów, system typów skrzyżowań, który ma logiczną interpretację i może reprezentować każdy normalizujący termin . Jak zauważyłeś, nie jest to dokładnie to samo, co ukończenie Turinga, ponieważ typ funkcji totalnej może wymagać aktualizacji (dopracowania) przed zastosowaniem jej do żądanego argumentu. Rachunek ten jest rachunkiem „w stylu curry'ego” i jest równy STLC + Γ ⊢ M : $\lambda$ i Γ⊢M:τ∩

   $$\frac{\Gamma\vdash M:\tau\quad \Gamma\vdash M:\sigma}{\Gamma\vdash M:\tau\cap\sigma}$$ Oczywiste jest, że „interpretacja”∩=∧prowadzi do spójnej interpretacji logicznej. $$\frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\tau}\quad \frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\sigma}$$ $\cap=\wedge$

2. Istnieje klasa systemów typów, Pure Type Systems , w których takie pytanie można by sprecyzować. W tych ramach logiczna interpretacja jest jednak mniej jasna. Można pokusić się o stwierdzenie: „PTS jest spójny, jeśli ma niezamieszkany typ”. Ale to nie działa, ponieważ typy mogą żyć w różnych „wszechświatach”, gdzie niektóre mogą być spójne, a inne nie. Coquand i Herbelin definiują pojęcie logicznych systemów typu czystego , w którym pytanie ma sens i pokazują

   Każdy niespójny, niezależny LPTS ma kombinator pętli (podobnie jak Turing Complete)

   Który odpowiada na pytanie w jednym kierunku (niespójne TC) w tym przypadku. O ile mi wiadomo, pytanie dotyczące ogólnego LPTS jest nadal otwarte i dość trudne.$\Rightarrow$

Edycja: Odwrotność wyniku Coquand-Herbelin nie jest tak łatwa, jak myślałem! Oto, co do tej pory wymyśliłem.

Logiczny Czysty Typ systemu jest PTS z (co najmniej) rodzaje i T y p e (co najmniej) Aksjomat p r o p : T y p e i (przynajmniej) zasada ( P r o p , P r o p , P r o p ) , z dalszym wymogiem, że nie ma rodzajów P r o p .$\mathrm{Prop}$$\mathrm{Type}$$\mathrm{Prop}:\mathrm{Type}$$(\mathrm{Prop},\mathrm{Prop},\mathrm{Prop})$$\mathrm{Prop}$

Teraz przyjmuję szczególne stwierdzenie o kompletności Turinga: napraw LPTS i niech Γ będzie kontekstem$L$$\Gamma$

oznaczaTuringa Całkowiteiff dla każdej całkowitej obliczalnej funkcji f : N → N istnieje termin t f taki, że Γ ⊢ t f : n a t → n a t i dla każdego n ∈ N t f ( S n 0 ) → ∗ β S f ( n )$L$$f:\mathbb{N}\rightarrow\mathbb{N}$$t_f$

Argument diagonalizacji Andreja pokazuje teraz, że nie ma końcówki typu n a $t$$\mathrm{nat}$ .

Teraz wydaje się, że jesteśmy w połowie drogi! Biorąc pod uwagę nie kończący się termin , chcemy zastąpić wystąpienia n a t jakimś ogólnym typem A i pozbyć się 0 i S w Γ , i będziemy mieć naszą niespójność ( A jest zamieszkały w kontekście A : P r o $\Gamma \vdash \mathrm{loop}:\mathrm{nat}$$\mathrm{nat}$$A$$0$$S$$\Gamma$$A$$A:\mathrm{Prop}$ )!

Niestety utknąłem w tym miejscu, ponieważ łatwo jest zastąpić literę tożsamością, ale zero jest znacznie trudniejsze do usunięcia. Idealnie chcielibyśmy skorzystać z jakiegoś twierdzenia o rekurencji Kleene'a, ale jeszcze tego nie rozgryzłem.$S$$0$

Oto odpowiedź na wariant precyzji @ cody mojego pytania. Istnieje spójny LPTS, który Turing kończy w sensie z grubsza @ cody, jeśli pozwolimy na wprowadzenie dodatkowych aksjomatów i reguł redukcji . Zatem ściśle mówiąc, system nie jest LPTS; jest to po prostu coś w rodzaju jednego.$\beta$

Zastanów się nad rachunkiem konstrukcji (lub swoim ulubionym członkiem kostki ). To jest LPTS, ale dodamy dodatkowe rzeczy, które sprawiają, że nie jest to LPTS. Wybierz stałe symbole nat , 0 , S i dodaj aksjomaty:$\lambda$$\text{nat}, 0, S$

⊢ 0 : nat ⊢ S : nat →

Indeks Turinga programy maszynowe według liczb naturalnych, a dla każdej liczby naturalnej wybrać symbol stałej f e , dodać aksjomat f e : nat → NAT , a dla wszystkich e , x ∈ N , dodaj p regułę -redukcja$e$$f_e$$f_e : \text{nat} \to \text{nat}$$e,x \in \mathbb{N}$$\beta$

gdzie normalnie ma wyjście E XX Turingowi programu maszyny o x . Jeśli Φ e ( x ) różni się wówczas reguła ta nie robi nic. Zauważ, że dodając te aksjomaty i reguły, twierdzenia systemu pozostają rekurencyjnie policzalne, chociaż jego zestaw reguł redukcji β nie jest już rozstrzygalny, a jedynie rekurencyjnie policzalny. Wierzę, że moglibyśmy z łatwością zachować zestaw $\Phi_e(x)$$e$$x$$\Phi_e(x)$$\beta$$\beta$ porządku reguł redukcji poprzez wyraźne określenie szczegółów modelu obliczeniowego w składni i regułach systemu.

Teraz teoria ta jest całkowicie ukończona w sensie z grubsza @ cody, tylko brutalną siłą; ale twierdzenie jest takie, że jest również spójne. Stwórzmy jego model.

Niech będą trzema zestawami, takimi, że:$U_1 \in U_2 \in U_3$

• (gdzie$\emptyset, \mathbb{N}, 0, S \in U_1$$S$ jest funkcją następczą).
• Każdy zestaw jest przechodni; jeśli , to a ∈ U $a \in b \in U_i$$a \in U_i$ .
• Każdy zestaw jest zamknięty pod tworzeniem przestrzeni funkcyjnych; tj. jeśli , to B A ∈ U $A, B \in U_i$$B^A \in U_i$ .
• $A \in U_i$$f : A \to U_i$$\prod_{a \in A} f(a) \in U_i$

$U_i$

$v$$U_2$$v$$I_v$

• $I_v(x) = v(x)$$x$
• $I_v(\ast) = U_1, I_v(\Box) = U_2$
• $I_v(\text{nat}) = \mathbb{N}, I_v(0) = 0, I_v(S) = S$
• $I_v(f_e) = \Phi_e$$\mathbb{N} \to \mathbb{N}$$e$
• $I_v(AB) = I_v(A)(I_v(B))$$I_v(A)$$I_v(B)$$I_v(AB) = 0$
• $I_v(\lambda x : A. B)$$a \in I_v(A)$$I_{v[x:=a]}(B)$
• $I_v(\Pi x : A. B) = \prod_{a \in I_v(A)} I_{v[x:=a]}(B)$

$A$$I_v(A) \in U_3$$v$$A : B$$v \models A : B$, gdyby $I_v(A) \in I_v(B)$. Mówimy tak$\Gamma \models A : B$ jeśli dla wszystkich interpretacji $v$, gdyby $v \models x : C$ dla wszystkich $(x : C) \in \Gamma$, następnie $v \models A : B$.

Łatwo jest sprawdzić, czy $\Gamma \vdash A : B$, następnie $\Gamma \models A : B$, więc jest to model systemu. Ale dla dowolnych zmiennych$x,y$, tak nie jest $y : \ast \models x : y$, ponieważ możemy interpretować $y$ przez $\emptyset$, więc system jest spójny.

To jest odpowiedź na moje pierwotne pytanie, w tym sensie, że rozsądnie jest nazywać kalulus na maszynie, który jest spójny i Turinga kompletny. Nie jest to jednak odpowiedź na pytanie @ cody, ponieważ nie jest to LPTS, ponieważ dodano dodatkowe aksjomaty i$\beta$zasady redukcji. Wyobrażam sobie, że odpowiedź na pytanie @ cody jest znacznie trudniejsza.