tisdag 1 mars 2016

Om Löbs sats och dess eventuella betydelse inom AI-forskning

Matematisk logik är långt ifrån det område av matematiken som jag har störst håg och fallenhet för, men jag blev för en tid sedan uppmärksammad på Löbs sats - en intressant släkting till Gödels båda ofullständighetssatser. På sidan 26 i sin bok Quantum Computing since Democritus (som jag rekommenderar mycket varmt och som jag alldeles säkert kommer att återkomma till här på bloggen) förklarar datalogen Scott Aaronson i omisskännlig stil vad satsen går ut på:
    If a statement can be proved by using as an axiom that it's provable, then it can also be proved without using that axiom. This result is known as Löb's Theorem [...], though personally I think that a better name would be the "You-Had-the-Mojo-All-Along Theorem".

Förutom att vara ett fantasieggande och förbluffande resultat i sig självt, så verkar det som om Löbs sats eventuellt kan vara av betydelse inom AI (artificiell intelligens), och mer specifikt ett potentiellt hinder för det slags AI-självförbättringsspiral som annars eventuellt kan väntas ge upphov till en intelligensexpolsion, även kallad Singulariteten. Åtminstone är det något man funderar intensivt över på MIRI - Machine Intelligence Research Institute, som är (den här på bloggen ofta citerade) Eliezer Yudkowskys skötebarn. MIRI-matematikern Patrick LaVictoire behandlar Löbs sats och dess eventuella AI-relevans i sin välskrivna översiktsuppsats An introduction to Löb's Theorem in MIRI research.

5 kommentarer:

  1. För mig som humanist låter Löbs sats i Aaronsons version som cirkulär. Men man måste kanske läsa uppsatsen ovan för att fatta?

    SvaraRadera
  2. När jag beställde din bok Here be Dragons så gav systemet mig ett tips på en annan bok som kunde intressera mig också. För en gång skull accepterade jag erbjudandet och köpte Quantum Computing since Democritus av Scott Aaronson.
    Uppskattar man sarkastiska / humoristiska diskussioner om Searle's Chineese Room, Penrose's Quantum consciousness, (i avd. sågningar), samt ; Turing, Free will, Beysian study of Anthropy and Doomsday etc. så är boken underhållande och på en hög nivå, (dvs. formler undviks ej).
    Som exempel kan jag nämna hur Aaronson studerar The Chineese Room bokstavligen. Regelboken som skulle "förstå" kinesiska skulle kunna vara en beskrivning av varenda neuron inblandad med en neuron beskriven på varje sida. Volymen på en sådan bok skulle bli ungefär som jordens volym!
    Vänliga hälsningar,
    Dan

    SvaraRadera
    Svar
    1. Ytterst glädjande (och för mig smickrande) att den nätbokhandel du använder dig av förknippar min bok med Aaronsons!

      Radera
  3. Löbs teorem är inte en "kusin" till Gödels sats utan helt enkelt den andra ofullständighetssatsen för ändliga extensioner (av någon teori man valt som bas). Varför man inte nöjer sig med att konstatera att "en maskin M_0 kan inte bevisa att dess förbättrade efterföljare M_1 inte bevisar motsägelser" utan hänvisar till Löb förstår jag inte efter en snabb titt på LaVictoires artikel.

    SvaraRadera