Jaka jest różnica między dowodami a programami (lub między propozycjami i typami)?

Biorąc pod uwagę, że Korespondencja Curry-Howarda jest tak szeroko rozpowszechniona / rozszerzona, czy istnieje jakaś różnica między dowodami a programami (lub między propozycjami i typami)? Czy naprawdę możemy je zidentyfikować?

Języki programowania, których ludzie używają na co dzień, nie pasują tak dobrze do korespondencji Curry-Howard, ponieważ ich systemy typów są zbyt słabe. Aby powiedzieć coś interesującego za pomocą Curry-Howarda dla programów imperatywnych, trzeba mieć bardziej wyrafinowany system pisma. Książka Adapting Proofs-as-Programs przesuwa ten kąt w celu syntezy programów imperatywnych. Ponieważ typy zależne stają się coraz bardziej popularne, z pewnością w badaniach języków funkcjonalnych ( Agda , Epigram ), rozróżnienie staje się coraz bardziej rozmyte. Oczywiście można przeprowadzić syntezę / ekstrakcję programu w ramach twierdzenia Coqa (i prawdopodobnie innych), które jest oczywiście oparte na Curry-Howardzie.

Korespondencję Curry-Howarda można również wykorzystać w sytuacjach, gdy proofy nie tak wyraźnie odpowiadają programom (lub nie są to programy, które ktokolwiek kiedykolwiek uruchomi). Jednym z przykładów jest autoryzacja dowodu . Twierdzenia odpowiadają stwierdzeniom o tym, kto jest do tego upoważniony. Dowody dostarczają wymaganych dowodów, że propozycja zawiera, dlatego wniosek o autoryzację jest dozwolony. W celu zakodowania dowodów wprowadzane są warunki sprawdzania (przez Curry-Howard). Warunki dowodu są wysyłane między stronami jako dowód potwierdzający ważność wniosków o autoryzację, ale nie są one uważane za programy.

W Coq istnieją 2 typy (Prop i Set), które są używane przez programistę do oddzielenia dowodów, które nie wygenerują rzeczywistego kodu oraz części dowodu, która zostanie użyta do wyodrębnienia działającego kodu (twojego programu).

To dobre rozwiązanie problemu, o który pytasz, jak zidentyfikować, co ma generować kod maszynowy (program) i co jest obecne, aby uzupełnić potwierdzenie propozycji (lub typu).

AFAIK nie ma automatycznego sposobu na rozróżnienie obu. To może być coś ciekawego do badań? A może ktoś jest w stanie wskazać, że jest to oczywiście niemożliwe?

W przypadku typów zależnych nie tylko nie ma wyraźnego rozróżnienia między proofami a programami, ale także nie ma rozróżnienia między programami i typami! Jedynym rozróżnieniem będzie miejsce, w którym pojawi się typ (lub program), co czyni go częścią miejsca „programu” lub miejsca „typu” danego terminu.

Przykład wyjaśni to, mam nadzieję:

Kiedy używasz funkcji tożsamości z typami zależnymi, musisz podać typ, z którym będziesz korzystać z funkcji! Ten typ jest używany jako wartość w twoim „programie”!

Untyped Lambda Calculus:

$\lambda{x}.x$

Z typami zależnymi:

id: (A: Set) -> A -> A

$(\lambda{A}.(\lambda{x}.x))$

Jeśli używasz tej funkcji, zrobiłbyś to tak jak w tym przykładzie:

id Naturals 1

Zauważ, że „typ” (w tym przypadku Zestaw Naturałów) przekazywany jako wartość jest wyrzucany, więc nigdy nie zostanie obliczony, ale nadal znajduje się w części „programowej” terminu. Tak też stanie się z częściami „sprawdzającymi”, które muszą być tam, aby sprawdzić typ, ale podczas obliczeń zostaną wyrzucone.

Wyjdę tutaj na całość i powiem, że jeśli zechcesz trochę zmrużyć oczy, można zidentyfikować dowody i programy kończące .

Każdy program kończący jest dowodem na to, że możesz wziąć jego dane wejściowe i wygenerować wyniki. Jest to bardzo podstawowy rodzaj dowodu na domniemanie.

Oczywiście, aby ta implikacja niosła informacje bardziej sensowne niż stwierdzanie oczywistych, musisz być w stanie wykazać, że program działa dla wszystkich instancji danych wejściowych z jakiejś klasy o logicznym znaczeniu. (I tak samo w przypadku danych wyjściowych.)

Z drugiej strony każdy dowód ze skończonymi krokami wnioskowania jest programem symbolicznym manipulującym obiektami w jakimś systemie logicznym. (Jeśli nie przejmujemy się zbytnio tym, co logiczne symbole i reguły oznaczają obliczeniowo).

$\exists x : x \vdash T$

Jest to dość uproszczone, ale myślę, że sugeruje solidność tego pomysłu. (Nawet jeśli niektórym ludziom się to nie spodoba. ;-))

Dowód nieistotności?

Kiedy piszesz jakiś program, jesteś zainteresowany jego wydajnością, zużyciem pamięci itp.
Np. Lepiej jest użyć sprytnego algorytmu sortowania zamiast sortowania bąbelkowego, nawet jeśli ich implementacje mają takie same typy (nawet przy ustawieniu typu zależnego).

Ale kiedy udowodnisz jakieś twierdzenie, interesuje cię tylko dowód.

Oczywiście, z estetycznego punktu widzenia, niektóre dowody są prostsze / piękne / inspirujące / itp. (Np. Dowody z Księgi).

Jeśli zaakceptujesz korespondencję Curry – Howard, to pytanie ma głównie charakter filozoficzny. „Czy proofy i programy są inne? Oczywiście. W jaki sposób? Cóż, nazywamy proofy„ proofami ”, a programy„ programami ”.”

Albo mówiąc mniej nonszalancko, jeśli istnieje dowód na istnienie izomorfizmu między dowodami a programami - co wydaje się wyraźnie, że istnieje - to pytanie brzmi, czy istnieje jakaś wyrocznia zdolna rozróżnić te dwa elementy. Ludzie klasyfikują je jako różne (w przeważającej części), więc z pewnością można argumentować, że taka wyrocznia istnieje. Ważnym pytaniem staje się zatem, czy istnieje jakaś znacząca różnica między nimi, która jest przedmiotem debaty filozoficznej. Co to jest „dowód”? Nie ma formalnej definicji tego, co stanowi dowód; jest to termin sztuki, podobnie jak pojęcie „skutecznie obliczalne” w tezie Kościoła i Turinga. W tym przypadku „program” również nie ma formalnej definicji.

Są to słowa języka naturalnego używane do kategoryzacji różnych dziedzin badań matematycznych. Curry i Howard zaobserwowali, że te dwie różne dziedziny faktycznie studiują to samo. Zauważenie tego połączenia jest ważne, ponieważ mówi, że ci różni badacze powinni ze sobą rozmawiać. Ale na innym poziomie, zauważenie związku to wiara w różnicę między nimi. Podczas rozwiązywania problemu czasem bardziej korzystne jest myślenie o nim jako o problemie programistycznym, a innym razem bardziej korzystne jest myślenie o nim jako o problemie logicznym. Ta różnica w perspektywie jest, moim zdaniem, istotną różnicą między nimi. Ale to, czy różnica perspektywy stanowi różnicę tożsamości, jest głębokim pytaniem filozoficznym, które zostało zbadane przynajmniej tak daleko jak FregeUeber Sinn und Bedeutung .