Kiedy (lub powinna) Teoretyczna CS dba o intuicyjne dowody?

Z tego, co rozumiem (co jest bardzo mało, więc proszę popraw mnie tam, gdzie się mylę!), Teoria języków programowania często dotyczy dowodów „intuicyjnych”. W mojej własnej interpretacji podejście to wymaga od nas poważnego potraktowania konsekwencji obliczeń dla logiki i sprawdzalności. Dowód nie może istnieć, chyba że istnieje algorytm konstruujący konsekwencje hipotez. Możemy na przykład odrzucić jako aksjomat zasadę wykluczonego środka, ponieważ pokazuje on jakiś obiekt, którym jest albo albo , niekonstruktywnie.$X$$\lnot X$

Powyższa filozofia może prowadzić nas do preferowania intuicyjnie ważnych dowodów od tych, które nie są. Nie widziałem jednak żadnych obaw związanych z faktycznym stosowaniem intuicyjnej logiki w artykułach z innych dziedzin teoretycznego CS. Wydaje się, że z przyjemnością potwierdzamy nasze wyniki za pomocą klasycznej logiki. Na przykład można sobie wyobrazić zastosowanie zasady wykluczonego środka w celu udowodnienia, że ​​algorytm jest poprawny. Innymi słowy, troszczymy się i poważnie traktujemy wszechświat ograniczony obliczeniowo w naszych wynikach, ale niekoniecznie w dowodach tych wyników.

1. Czy badacze teoretycznego CS kiedykolwiek martwią się pisaniem poprawnych intuicyjnie dowodów? Mogę łatwo wyobrazić sobie dziedzinę informatyki teoretycznej, która stara się zrozumieć, kiedy wyniki TCS, zwłaszcza algorytmiczne, trzymają się intuicyjnej logiki (lub, co bardziej interesujące, kiedy nie). Ale jeszcze nie spotkałem.

2. Czy istnieje jakiś filozoficzny argument, że powinni? Wydaje się, że można twierdzić, że wyniki informatyki powinny być udowodnione intuicyjnie, jeśli to możliwe, i powinniśmy wiedzieć, które wyniki wymagają np . PEM. Czy ktoś próbował wysunąć taki argument? A może istnieje konsensus, że to pytanie nie jest po prostu bardzo ważne?

3. Jako pytanie poboczne ciekawi mnie przykłady przypadków, w których to tak naprawdę ma znaczenie: Czy istnieją znane wyniki TCS w logice klasycznej, ale nie w logice intuicyjnej? Lub podejrzewa się, że nie trzyma się intuicyjnej logiki.

Przepraszamy za miękkość pytania! Może wymagać przeredagowania lub reinterpretacji po wysłuchaniu ekspertów.

Jak powiedziałem w komentarzach, logika intuicyjna nie jest najważniejsza. Ważniejszym punktem jest posiadanie konstruktywnego dowodu. Myślę, że teoria typów Martina-Löfa jest o wiele bardziej istotna dla teorii języka programowania niż logika intuicyjna i są eksperci, którzy twierdzili, że praca Martina-Löfa jest głównym powodem ożywienia ogólnego zainteresowania matematyką konstruktywną.

Obliczeniowa interpretacja konstruktywności jest jedną z możliwych perspektyw, ale nie jest jedyną. Powinniśmy zachować ostrożność, gdy chcemy porównać konstruktywne dowody z dowodami klasycznymi. Chociaż oba mogą używać tych samych symboli, to co oznaczają te symbole, są różne.

Zawsze warto pamiętać, że dowody klasyczne można przełożyć na dowody intuicyjne. Innymi słowy, w pewnym sensie logika klasyczna jest podsystemem logiki intuicyjnej. Dlatego możesz w pewnym sensie zrealizować (powiedzmy przy użyciu funkcji obliczalnych) klasyczne dowody. Z drugiej strony możemy myśleć o konstruktywnej matematyce jako o jakimś systemie matematycznym w klasycznym otoczeniu.

Na koniec formalizmy, klasyczne lub konstruktywne, są dla nas narzędziem do wyrażania wypowiedzi. Przyjmowanie klasycznego twierdzenia i próba konstruktywnego udowodnienia go bez tej perspektywy nie ma większego sensu IMHO. Kiedy mówię klasycznie mam na myśli coś innego od tego, co mówię, konstruktywnie. Możesz spierać się o to, co „powinno” być prawdziwym znaczeniem „ ”, ale myślę, że nie jest to interesujące, jeśli nie rozmawiamy o tym, co chcemy wyrazić. Czy mamy na myśli (przynajmniej) jedną z nich i wiemy, która? Czy może po prostu mamy na myśli jedną z nich?A ∨ B $A \lor B$$A \lor B$$\lor$

Teraz, z tego punktu widzenia, jeśli chcemy udowodnić oświadczenie jak i chcemy odnosić się to do mapowania z w pewnym spełniającej wówczas lepszym sposobem wyrażenia może być sposób konstruktywny. Z drugiej strony, jeśli zależy nam tylko na istnieniu a nie na tym, jak je znaleźć, wówczas klasyczny sposób prawdopodobnie miałby większy sens. Kiedy konstruktywnie udowodnisz instrukcję, niejawnie budujesz również algorytm znajdowania z . Możesz zrobić to samo, używając bardziej skomplikowanej formuły, takiej jak: „algorytm ma właściwość, która dla wszystkichx y φ ( x , y ) y y x A x φ ( x , A ( x ) ) $\forall x \ \exists y \ \varphi(x,y)$$x$$y$$\varphi(x,y)$$y$$y$$x$$A$$x$ , "gdzie jest jawnie podanym algorytmem. Jeśli nie jest jasne, dlaczego można preferować konstruktywny sposób wyrażenia tego, pomyśl o językach programowania jako analogii: możesz napisać program dla algorytmu MST Kruskala w asemblerze x86, w którym musisz dbać o wiele problemów ubocznych lub możesz napisać program w Pythonie.$\varphi(x,A(x))$$A$

Dlaczego więc nie używamy logiki intuicyjnej w praktyce? Jest kilka powodów. Na przykład większość z nas nie jest wyszkolona z tym nastawieniem umysłu. Znalezienie klasycznego dowodu stwierdzenia może być znacznie łatwiejsze niż znalezienie konstruktywnego dowodu. Lub możemy dbać o szczegóły niskiego poziomu, które są ukryte i niedostępne w konstruktywnym ustawieniu (patrz także logika liniowa ). Lub możemy po prostu nie być zainteresowani uzyskaniem dodatkowych rzeczy, które pochodzą z konstruktywnym dowodem. I chociaż istnieją narzędzia do wyodrębniania programów z dowodów, narzędzia te na ogół wymagają bardzo szczegółowych dowodów i nie były wystarczająco przyjazne dla użytkownika dla teoretyków ogólnych. Krótko mówiąc, za dużo bólu za mało korzyści.

Oto jeden z możliwych powodów, dla których nie widzimy zbyt wielu konstruktywnych dowodów w teorii A: nasze twierdzenia w teorii A są często twierdzeniami i są udowodnione przy użyciu niezbyt mocnych teorii (powiedzmy, że są one możliwe do udowodnienia w ) i meta -twierdzenie, że wszystkie z nich są również możliwe do udowodnienia konstruktywnie (w konstruktywnym odpowiedniku ). W rzeczywistości wiele wyników teorii A można udowodnić w teoriach znacznie słabszych niż . P A P A P $\Pi^0_2$$PA$$PA$$PA$

Pamiętam, że Douglas S. Bridges we wstępie do swojej książki teorii obliczeń argumentował, że powinniśmy konstruktywnie udowodnić nasze wyniki. Podaje przykład, który IIRC jest zasadniczo następujący:

Załóżmy, że pracujesz dla dużej firmy programistycznej, a Twój menedżer prosi o program umożliwiający rozwiązanie problemu. Czy akceptowalny byłby powrót z dwoma programami i poinformowanie swojego menedżera o jednym z tych dwóch rozwiązań poprawnie, ale nie wiem który?

Na koniec powinniśmy pamiętać, że chociaż używamy tych samych symboli dla klasycznej i intuicyjnej logiki, symbole te mają różne znaczenia, a jeden z nich zależy od tego, co chcemy wyrazić.

Jeśli chodzi o twoje ostatnie pytanie, myślę, że twierdzenie Robertsona-Seymour'a byłoby przykładem twierdzenia, o którym wiemy, że jest prawdziwe klasycznie, ale nie mamy na to żadnego konstruktywnego dowodu. Zobacz też

• Czy istnieją dowody istnienia niekonstruktywnego algorytmu?

Warto zastanowić się, DLACZEGO intuicyjna logika jest naturalną logiką obliczeniową, ponieważ zbyt często ludzie gubią się w szczegółach technicznych i nie rozumieją istoty problemu.

Bardzo prosto, logika klasyczna jest logiką doskonałej informacji: zakłada się, że wszystkie instrukcje w systemie są znane lub można je poznać jako jednoznacznie prawdziwe lub fałszywe.

Z drugiej strony, logika intuistionistyczna ma miejsce na wypowiedzi o nieznanych i nieznanych wartościach prawdy. Ma to zasadnicze znaczenie dla obliczeń, ponieważ dzięki nierozstrzygalności zakończenia w ogólnym przypadku nie zawsze będzie pewne, jaka będzie wartość prawdy niektórych zdań, a nawet czy wartość prawdy może być kiedykolwiek przypisana do niektórych instrukcji .

$\neg\neg P \implies P$

Moim zdaniem te „semantyczne” powody są o wiele ważniejszą motywacją do korzystania z intuicyjnej logiki do obliczeń, niż jakiekolwiek inne techniczne powody, które można by wprowadzić.

Rzeczywiste funkcje skrótu kryptograficznego, takie jak MD5 i SHA, nie wymagają użycia klucza. W związku z tym bardzo trudno jest zastosować techniki od teoretycznej kryptografii do uzasadnienia ich bezpieczeństwa. Prosty powód, dla którego: dla dowolnej funkcji skrótu bez klucza istnieje bardzo mały program / przeciwnik, który powoduje kolizję w ramach tej funkcji skrótu; mianowicie program, który ma taką kolizję - która musi istnieć! -- mocno zakodowane.

Artykuł Phila Rogaway'a Formalizowanie ludzkiej niewiedzy: Odporne na zderzenia mieszanie bez kluczy zajmuje się tym problemem. Pokazuje on, że niektóre bardzo standardowe twierdzenia dotyczące kluczowych funkcji skrótu (takie jak konstrukcja Merkle-Damgård i paradygmat skrótu-wtedy-znak) można dostosować i ponownie udowodnić za pomocą „twierdzeń przyjaznych intuicjonistom” odnoszących się do nieskróconych funkcji skrótu.

tutaj jest ładny rozdział na temat logiki intuicyjnej z obszernej książki online Logic for Computer Science , 300pp. [1] sekcja 9.5, p210, streszczenie na p220:

Logika intuicyjna powstała z konstruktywistycznego ruchu w matematyce, który odrzucił niekonstruktywne dowody istnienia lub te oparte na prawie wykluczonego środka. Ostatnio związek między intuicyjną matematyką a programowaniem wynika z obserwacji, że zdania i typy (w sensie programowania) są równoważne. Opracowanie algorytmu w tym systemie formalnym, opartym na naturalnej dedukcji, polega na napisaniu specyfikacji w notacji logicznej, a następnie, uznaniu jej za typ, udowodnieniu, że nie jest pusta. Ponieważ leżąca u podstaw logika jest konstruktywnym dowodem, jeśli można ją przeprowadzić,

inna pobliska perspektywa pochodzi od TCSist Andreja Bauera piszącego o „Matematyki i obliczeniach; matematyka dla komputerów” [2], który zasadniczo twierdzi, że „matematyka intuicyjna jest dobra dla fizyki”. prezentacja dotyczy głównie fizyki, ale dla tych, którzy uważają, że CS jest ściśle powiązane z fizyką, ideologia na ogół przeniesie się do TCS.

Interpretacja obliczeniowa. Jest to interpretacja intuicyjnej logiki powszechnie prezentowanej w informatyce. Uważamy wszystkie zestawy za reprezentowane przez odpowiednie struktury danych - rozsądny punkt widzenia dla informatyka. Następnie uznaje się stwierdzenie za prawdziwe, jeśli istnieje program (dowód obliczeniowy) świadczący o jego prawdziwości.

[1] Logika dla informatyki, Reeves i Clark

[2] Intuicyjna matematyka dla fizyki Bauer