Disputas: Mathias Barra

Prøveforelesning

Bedømmelseskomité

U-Hoofdosent Andreas Weiermann, Ghent University
Professor Isabel Oitavem, Universidade Nova de Lisboa
Professor Herman Ruge Jervell, UiO

Leder av disputas:  Instituttleder Arne Bang Huseby

Veileder:  Lars Kristiansen og Dag Normann

Sammendrag

Avhandlingen besvarer spørsmål av typen ”hvor vanskelig er det egentlig å utføre denne beregningen?”.

I siste kapittel løser forfatteren og medforfatter Philipp Gerhardy et 53 år gammelt uløst problem, og dette er et av de mest oppsiktsvekkende resultatene. Problemet ble opprinnelig formulert av den norske logikeren Thoralf Skolem – logikkens Abel – og dreier seg om hvordan en viss mengde matematiske funksjoner er ordnet. En slik ordning kan ikke beskrives med vanlige tall: man må ty til uendelig store ordinaltall. Dette gjør arbeidet med å beregne ordningens type meget komplisert, og graden av uendelighet blir et mål på hvor innfløkt ordningen er.

En annen problemstilling er hvilke beregninger som lar seg gjennomføre dersom man må begrense seg til kun å bruke relativt små tall. Her har forfatteren oppdaget flere nye måter å beskrive velkjente kompleksitetsklasser på. Ett hovedresultat er at subtraksjon (minus) i visse sammenhenger gir like mye regnekraft som addisjon (pluss). Dette høres kanskje selvsagt ut, men for noen typer abstrakte regnemaskiner – eller datamaskiner – er det nokså komplisert å oversette et program som kan addere, til et program som kun kan subtrahere. Det har vært ukjent frem til nå om det overhodet lot seg gjøre. Tilsvarende arbeid er også gjort for multiplikasjon (gange). Her viser det seg at divisjon (deling) ikke er nok; man må også ha tilgang til å kunne finne ”divisjonsresten”.

Forskningen er utført over en fireårsperiode ved Matematisk institutt ved Universitetet i Oslo. Avhandlingen innholder flere nye resultater innen matematisk logikk; et felt som er nært beslekted med teoretisk informatikk. Avhandlingen er utformet som en lengre monograf (197 sider), der tre tidligere publiserte artikler er innarbeidet som en del av teksten Mye av arbeidet har også vært presenter underveis på konferanseserien Computability in Europe, der forfatteren har holdt foredrag hvert år siden 2005.

Kontaktperson

For mer informasjon, kontakt Robin Bjørnetun Jacobsen.