Pytania otagowane jako constructive-mathematics

4
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 …
3
Konstruktywnie wydajne algorytmy bez sprawdzania poprawności i wydajności
Szukam naturalnych przykładów wydajnych algorytmów (tj. W czasie wielomianowym) ul ich poprawność i skuteczność można konstruktywnie udowodnić (np. w lub ), alePRAPRAPRAHAHAHA nie jest znany żaden dowód wykorzystujący tylko wydajne koncepcje (tzn. nie wiemy, jak udowodnić ich poprawność i wydajność w lub ).TV0TV0TV^0S12S21S^1_2 Mogę samodzielnie tworzyć sztuczne przykłady. Chcę jednak …
1
Co sprawia, że ​​język (i jego system typów) jest w stanie udowodnić twierdzenia o swoich terminach?
Niedawno próbowałem zaimplementować Cedille-Core Aarona , minimalistyczny język programowania zdolny do udowodnienia twierdzeń matematycznych na temat własnych terminów. Udowodniłem również indukcję dla typów danych zakodowanych na λ, co wyjaśniło, dlaczego jego rozszerzenia byłyby konieczne. Nie mówiąc już o tym, wciąż zastanawiam się, skąd pochodzą te rozszerzenia. Dlaczego są tacy, jacy …
1
Równość rozstrzygalnych dowodów?
Chcę wiedzieć, czy rozstrzygalność o równości dwóch rozstrzygalnych dowodów tej samej twierdzenia można udowodnić bez żadnych dodatkowych aksjomatów w rachunku konstrukcji indukcyjnych. W szczególności chcę wiedzieć, czy to prawda bez żadnych dodatkowych aksjomatów w Coq. ∀ P.: Prop , P∨ ¬ P⇒ ( ∀p1: P, ∀p2): P, {p1=p2)} ∨ {p1≠p2)} …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.