Vuonna matematiikka , logiikka, ja tietojenkäsittelytiede , tyyppi teoria on luokan muodollista järjestelmien , joista jotkut voivat toimia vaihtoehtoina joukkoteorian kuin matematiikan perusteet . Karkeasti sanottuna tyyppi on niiden ominaisuuksien "karakterisointi", jotka termi täyttää. Tyyppiteoriassa jokaisella termillä on tyyppi ja järjestelmän kuvaamat toiminnot asettavat rajoituksia yhdistettävien termien tyypille.
Tyyppinen teoria liittyy läheisesti (ja joskus päällekkäin) tutkimuksessa tyypin järjestelmiä , joita käytetään joissakin ohjelmointikieliä , jotta vältetään tiettyjä vikoja . Kuitenkin historiallisesti tyyppisiä teorioita otettiin käyttöön estämään muodollisen logiikan paradokseja, ja termi "tyyppiteoria" viittaa usein tähän laajempaan kontekstiin.
Kaksi esiin nousevan tyyppistä teoriaa voi toimia matematiikan perustana; nämä ovat Alonzo Churchin kirjoittama λ-laskenta ja Per Martin-Löfin intuitionistinen tyyppiteoria . Oli miten on, logiikkien luomat tyyppiteoriat löytävät suuren sovelluksen useimpien todistusavustajien aksiomaattisina järjestelminä, koska Curry-Howard-kirjeenvaihto yhdistää todisteet ja ohjelmat.
Vuodesta näkökulmasta matemaattinen teoria: tyypit olivat ensimmäiset teoretisoineet Bertrand Russell vastauksena hänen löytö paradoksi heikentää naiivi joukko-opin ja Gottlob Frege . Tämäntyyppinen teoria on kehitetty Principia Mathematica mukaan Russell ja Whitehead . Sen avulla Russellin paradoksi voidaan kiertää ottamalla ensin käyttöön tyyppihierarkia ja määrittämällä sitten tyyppi jokaiselle matemaattiselle kokonaisuudelle. Tietyntyyppiset objektit voidaan rakentaa vain esineistä, jotka ovat jo olemassa (sijaitsevat hierarkiassa matalammin), mikä estää loputtomien silmukoiden ja paradoksien syntymisen ja rikkoo teoriaa.
Mitä tulee matematiikan osa-alueeseen, jota kutsutaan matemaattiseksi logiikaksi - mutta se on myös erittäin hyödyllinen tietojenkäsittelytieteiden aloilla, kielioppien teorialle, kokoomateoriaksi ja uudelleenkirjoittamisjärjestelmälle, vielä viime aikoina transkompilaation alalla - me käyttää tyyppejä tyyppiteorian puitteissa.
Jokapäiväisessä kielessä "tyyppiteoria" on ymmärrettävä uudelleenkirjoittamisjärjestelmien yhteydessä . Tunnetuin esimerkki on lambdakalkyyli alkaen Alonzo Church . Hänen teoria tyypit mahdollisti siirtää alkuperäisestä tyypittömässä hammaskiveä, sekavaa koska sen Kleenen-Rosser paradoksi (in) , joka oikein hammaskiven . Kirkko osoitti, että tämä järjestelmä voisi toimia matematiikan perustana; sitä kuvataan korkeamman asteen logiikaksi .
Muut merkittävien tyyppien teoriat ovat intuitionistista tyyppiteoriaa. Per Martin-Löfiä käytetään perustana joillekin konstruktivistisen matematiikan aloille ja todistusavustajille, kuten Agda (in) tai Idris . Laskeminen on Thierry Coquand: n rakenteet ja sen laajennukset käytetään erityisesti Coq ja Matita (fi) . Tämä on aktiivista tutkimusta, kuten homotooppityyppiteorian viimeaikainen kehitys osoittaa .
Bertrand Russell loi ensimmäisen tyyppisen teorian (nimeltään ”haarautunut”) loogisten paradoksien, kuten valehtelijan ja joukko-teorian , ratkaisemiseksi . hankala käyttää, se on ensin yksinkertaistaa Ramsey sitten korvattu Zermelo-Frankel teoria in 1922 (itsestään selvää, emäs, jota kaikki matemaatikot, muut NF teoria raskaaksi Quinen vuonna 1937 ja täydelliseksi NFU vuonna 1969 Ronald Jensen ei käytetä matemaatikot sen tarjoamista yksinkertaistamismahdollisuuksista huolimatta, katso Uudet säätiöt ), ja harkitsi myös alkeellisempia objekteja lambda-laskennan ja kombinatorisen logiikan löytämisen jälkeen . Vaikka nämä teoriat ovat johdonmukaisia alkuperäisissä versioissaan, jotka ovat kirjoittamattomia, on mielenkiintoista tutkia formulaatioita tyypeillä.
Jälkimmäisissä tapauksissa matemaattiset entiteetit rakennetaan funktioiden avulla , jolloin jokaisella funktiolla on tyyppi, joka kuvaa sen argumenttien tyypin ja palautetun arvon tyypin. Entiteetit ovat hyvin muodostuneita, kun funktioita käytetään kohteisiin, joiden tyyppi on funktion odotettavissa.
Tyypin käsitteellä on useita sovellusaloja: