Dlaczego Martin-Löf potrzebował stworzyć intuicyjną teorię typów?


13

Czytałem o Intuitionistic Type Theory (ITT) i to ma sens. Ale staram się zrozumieć, dlaczego „dlaczego” zostało stworzone?

Intuicyjna logika (IL) i prosty typ rachunek (STLC) i teoria typów ogólnie poprzedzają samo istnienie samego Martina-Löfa! Wydaje się, że w STLC można zrobić wszystko, co jest możliwe w ITT (mogę się mylić, ale przynajmniej tak się czuje). λ

Czym więc była „nowość” w ITT i jak dokładnie (lub czy) rozwinęła teorię obliczeń? Z tego, co rozumiem, wprowadził pojęcie „typów zależnych”, ale wydaje się, że były one już w pewnym sensie w STLC. Czy jego ITT była próbą abstrakcji, aby zrozumieć razem podstawowe zasady STLC i IL? Ale czy STLC już tego nie zrobiło? Dlaczego w ogóle stworzono ITT? Jaki był / miał sens?

Oto fragment z Wikipedii : Ale wciąż nie mam powodu, dla którego nie powstał wcześniej.

Pierwszy szkic artykułu Martina-Löfa na temat teorii typów pochodzi z 1971 roku. Ta impredykatywna teoria uogólniła system F. Girarda. Jednak system ten okazał się niespójny ze względu na paradoks Girarda, który odkrył Girard podczas badania Systemu U, niespójnego rozszerzenia Systemu F. Doświadczenie to doprowadziło Per Martina-Löfa do opracowania filozoficznych podstaw teorii typów, wyjaśnienia jego znaczenia, formy semantyki dowodowej, która uzasadnia predykatywną teorię typów, przedstawioną w jego książce Bibliopolis z 1984 roku ...

Z fragmentu wydaje się, że powodem było rozwinięcie „ filozoficznych podstaw teorii typów ” - myślałem, że ten fundament już istnieje (a może tak przypuszczałem). Czy to był zatem główny powód?


1
Jeśli dobrze pamiętam, powód, dla którego to zrobił, był nieco filozoficzny (konstruktywny fundament matematyki), a nie tylko techniczny, ale minęło już trochę czasu, odkąd uczestniczyłem w jego wykładach i nie mam przy sobie notatek w górę. Dobrym miejscem do spojrzenia w górę, aby lepiej zrozumieć pracę Martina-Lofa i jej porównanie z innymi teoriami, są „Podstawy matematyki konstrukcyjnej” Beesona. Ma rozdział poświęcony temu.
Kaveh

1
ps: możesz zredagować tytuł, aby pasował do tego, o co pytasz w ciele, teraz tytuł wydaje się pytać, co było nowością w teorii Martina-Lofa, podczas gdy ciało wydaje się pytać, dlaczego to zrobił.
Kaveh

Odpowiedzi:


24

λ

  • Wykorzystanie reguły Leibniza dotyczącej tożsamości nierozróżnialnych do zakodowania równości zdań. Takie podejście jest stosowane w rachunku konstrukcji, ale wymaga impredykatywnych wszechświatów, które zostały odrzucone przez Martina-Löfa z powodów filozoficznych.

  • Bezpośrednia konstruktywna charakterystyka równości. Nadanie takiej charakterystyki przy użyciu typów tożsamości może być główną nowością intuicyjnej teorii typów Martina-Löfa.

Typy tożsamości wydają się dziś zwodniczo proste, ale ponownie skupiły się na zrozumieniu teorii typów częściowo dlatego, że dały początek intrygującym pytaniom semantycznym, takim jak: czy dowody tożsamości są unikalne? W pewnym sensie pytanie to prowadzi do teorii typu homotopii i aksjomatu jedności (który jest niezgodny z wyjątkowością tożsamości). Hofmann i Streicher pokazali, że wyjątkowości dowodów tożsamości nie da się wyprowadzić z intuicyjnej teorii typów Martina-Löfa w: „Grupoidoidalna interpretacja teorii typów”. Nawiasem mówiąc, wynik ten pokazuje również, że dopasowanie wzorca nie jest konserwatywnym rozszerzeniem tradycyjnej teorii typów.

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.