Teoria wykonalności: różnica mocy między rachunkiem lambda a maszynami Turinga

48

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 ma obliczyć liczbę reprezentującą maszynę Turinga na podstawie terminu lambda reprezentującego funkcję f. Tego nie da się zrobić (wyjaśnię dlaczego, jeśli zadacie to jako osobne pytanie).

  • Chciałbym zobaczyć wyjaśnienie / nieformalny dowód.

Nie widzę tu zastosowania twierdzenia Rice'a; miałoby to zastosowanie do problemu „czy ta maszyna Turinga i ten równoważnik L lambda?”, ponieważ zastosowanie tego predykatu do równoważnych terminów daje ten sam rezultat. Wymagana funkcja może jednak obliczać różne, ale równoważne, bazy TM dla różnych, ale równoważnych terminów lambda.

  • Co więcej, jeśli problem dotyczy introspekcji terminu lambda, myślę, że przekazanie kodowania Gödela terminu lambda byłoby również dopuszczalne, prawda?

Z jednej strony, biorąc pod uwagę, że jego przykład dotyczy obliczania, w rachunku lambda, liczby kroków wymaganych przez maszynę Turinga do wykonania danego zadania, nie jestem bardzo zaskoczony.

  • Ale ponieważ tutaj rachunek lambda nie może rozwiązać problemu związanego z maszyną Turinga, zastanawiam się, czy można zdefiniować podobny problem dla rachunku lambda i udowodnić, że jest on nierozwiązywalny dla maszyn Turinga, czy faktycznie istnieje różnica w mocy na korzyść Maszyny Turinga (co by mnie zaskoczyło).
Blaisorblade
źródło

Odpowiedzi:

56

John Longley ma bardzo obszerny artykuł ankietowy omawiający związane z tym kwestie, „Pojęcia obliczalności w wyższym typie” .

Podstawową ideą jest to, że teza Churcha-Turinga dotyczy tylko funkcji z - i jest więcej do obliczeń! W szczególności, kiedy piszemy programy, korzystamy z funkcji wyższego typu (takich jak ( NN ) N ).NN(NN)N

Aby w pełni zdefiniować model obliczeń wyższego typu, musimy określić konwencję wywoływania funkcji, aby jedna funkcja mogła wywoływać inną funkcję otrzymaną jako argument. W rachunku lambda standardowa konwencja wywoływania polega na tym, że reprezentujemy funkcje według terminów lambda, a jedyne, co można zrobić z lambda w rachunku lambda, to zastosować go. W typowych kodowaniach z maszynami Turinga przekazujemy funkcje jako argumenty, ustalając konkretne kodowanie Godela, a następnie łańcuchy reprezentujące indeks maszyny, którą chcesz przekazać jako argument.

Różnica w kodowaniu oznacza, że ​​możesz analizować składnię argumentu za pomocą kodowania w stylu TM, a nie możesz ze standardową reprezentacją rachunku lambda. Jeśli więc otrzymujesz termin lambda dla funkcji typu , możesz przetestować jego zachowanie, przekazując mu określone n - nie możesz w żaden sposób analizować struktury tego terminu. To po prostu za mało informacji, aby zrozumieć kod terminu lambda.NNn

Warto zauważyć, że przy wyższych typach, jeśli język jest mniej ekspresyjny przy jednym rzędzie, jest bardziej ekspresyjny o jeden rząd w górę, ponieważ funkcje są sprzeczne. Podobnie są funkcje, które można pisać w LC, których nie można kodować w stylu TM (ponieważ polegają one na tym, że można przekazywać argumenty funkcjonalne i wiedzieć, że odbiornik nie może zajrzeć do funkcji, którą dajesz) .

EDYCJA: Oto przykład funkcji definiowanej w PCF, ale nie w kodowaniu TM + Goedel. Zadeklaruję isAlwaysTruefunkcję

 isAlwaysTrue : ((unit → bool) → bool) → bool

który powinien zwracać wartość true, jeśli jego argument ignoruje argument i zawsze zwraca wartość true, powinien zwracać wartość false, jeśli argument zwraca wartość false na dowolnym wejściu, i przechodzi do pętli, jeśli jego argument przechodzi do pętli na dowolnym wejściu. Możemy dość łatwo zdefiniować tę funkcję w następujący sposób:

isAlwaysTrue p = p (λ(). true) ∧ p (λ(). false) ∧ p (λ(). ⊥)

gdzie jest obliczeniem zapętlenia i jest operatorem i na booleanach. Działa to, ponieważ unit → boolw PCF są tylko trzej mieszkańcy , dlatego możemy je wyczerpująco wyliczyć. Jednak w modelu stylu + kodowania Goedela TM pmoże sprawdzać, ile czasu zajmuje jego argument, aby zwrócić odpowiedź, i na tej podstawie zwracać różne odpowiedzi. W związku z tym wdrożenie za isAlwaysTruepomocą baz TM nie spełniłoby specyfikacji.

Neel Krishnaswami
źródło
1
to doskonała ankieta. dzięki za link!
Suresh Venkat
Właśnie zdałem sobie sprawę, że zapomniałem przyjąć odpowiedź, chociaż chciałem zaakceptować twoją. Przepraszam!
Blaisorblade,
„Różnica w kodowaniu oznacza, że ​​możesz analizować składnię argumentu za pomocą kodowania w stylu TM, a nie możesz ze standardową reprezentacją rachunku lambda.”: Ale jeśli masz reprezentacje dla składu funkcji? Ponadto, to, co mówisz, wydaje się sugerować, że HOL jest czymś więcej niż teorią rachunku lambda na maszynie, to coś więcej?
Hibou57
A co z tym: cs.virginia.edu/~evans/cs150/classes/class39/lecture39.pdf . Czy to w jakiś sposób jest złe?
Hibou57
Drogi Neelu, czy masz przykład funkcji, która może być realizowana w modelu rachunku lambda, ale nie w modelu Turinga?
Ingo Blechschmidt
29

Co powiedziała Neel, a także następujące.

NNλλλ

λNN


λNNλ

NNλappn¯f:NNf(k)appn¯k¯n¯nappλ

Xf:X×NNλtf~:X(NN)λsXNNλff~NNλλNNλ

XNNλXX

Andrej Bauer
źródło
2
wciąż czekam na lepszy przykład ...
Jacques Carette,
1
λ
Nie rozumiem, jak curry może stać się nieporównywalne. Powinieneś być w stanie ponownie wykorzystać twierdzenie smn, ponieważ jego dowód konstruuje funkcję na danych pierwszego rzędu (naturals). Według tezy Church-Turinga takie zachowanie na naturach może być zaimplementowane jako termin lambda (który używa wewnętrznych funkcji rodzimych, ale nie rozumiem, jak to jest zabronione). Podobnie można udowodnić twierdzenie utm, więc zgodnie z twoim postem powinniśmy to zrobić. czego mi brakuje?
Blaisorblade,
1
W odpowiedzi wyjaśniłem, co to znaczy, że curry staje się niepoliczalne, a mianowicie, że sugerowany obiekt nie jest wykładniczy w kategorii reprezentowanych zbiorów.
Andrej Bauer,
Dziękuję za wyjaśnienie! Niestety nie mogę ponownie głosować. Potrafię śledzić większość szczegółów technicznych; Nie znam modeli topologicznych, ale w każdym razie jestem zaznajomiony z „nie można sprawdzać funkcji w programowaniu funkcjonalnym / rachunku λ”. W ostatnim akapicie wyjaśniono również, dlaczego nie mogę przejść przez smn, ponieważ curry podane przez smn ponownie generuje kody Gödela, a nie standardowe funkcje, jakich potrzebujesz. Będę medytować nad tym akapitem.
Blaisorblade,