Är datorer redo att lösa detta notoriskt svårhanterliga matematiska problem?

Ms Tech | SuperRembo via codingtrain

Datavetaren Marijn Heule är alltid på jakt efter en bra matematisk utmaning. En docent vid Carnegie Mellon University, Heule har ett imponerande rykte för att lösa svårlösta matematiska problem med beräkningsverktyg. Hans resultat 2016 med det booleska pythagoreiska trippelproblemet var ett enormt rubrik-gripande bevis: Tvåhundra terabyte mattebevis är det största någonsin . Nu använder han ett automatiserat tillvägagångssätt för att attackera den förtrollande enkla Collatz-förmodan.

Först föreslogs (enligt vissa uppgifter) på 1930-talet av den tyske matematikern Lothar Collatz, ger detta talteoretiska problem ett recept, eller algoritm, för att generera en numerisk sekvens : Börja med vilket positivt heltal som helst. Om talet är jämnt, dividera med två. Om talet är udda, multiplicera med tre och lägg till en. Och sedan göra samma sak, igen och igen. Gissningen hävdar att sekvensen alltid kommer att hamna på 1 (och sedan kontinuerligt cykla genom 4, 2, 1).

Siffran 5, till exempel, genererar bara sex termer:

5, 16, 8, 4, 2, 1

Siffran 27 cyklar genom 111 termer, svänger upp och ner – på sin höjd och når 9 232 – innan den slutligen landar på 1.

Siffran 40 genererar en annan kort sekvens:

40, 20, 10, 5, 16, 8, 4, 2, 1

Hittills har gissningen kontrollerats av dator för alla startvärden upp till nästan 300 miljarder miljarder och varje nummer når så småningom 1.

De flesta forskare tror att gissningarna är sanna. Det har lockat mängder av matematiker och icke-matematiker likadana, men ingen har tagit fram ett bevis. I början av 1980-talet förklarade den ungerske matematikern Paul Erdős: Matematiken är ännu inte redo för sådana problem.

Det vi vill veta är om människor eller datorer är bättre på att lösa sådana problem.

Marijn Heule

Och han har nog rätt, säger Heule. För Heule är Collatz tjusning inte så mycket utsikten till ett genombrott som det är att utveckla automatiserade resonemangstekniker. Efter att ha pysslat med det i fem år, publicerade Heule och hans medarbetare, Scott Aaronson och Emre Yolcu, nyligen en papper på arXiv preprint-server. Även om vi inte lyckas bevisa Collatz-förmodan, skriver de, tror vi att idéerna här representerar ett intressant nytt tillvägagångssätt.

Det är ett ädelt misslyckande, säger Aaronson, en datavetare vid University of Texas i Austin. Ett misslyckande eftersom de inte bevisade gissningen. Nobel eftersom de gjorde framsteg i en annan mening: Heule ser det som en utgångspunkt för att avgöra om människor eller datorer är bättre på att bevisa sådana problem.

Att översätta matematik till beräkning

För många matematiska problem är datorer hopplösa, eftersom de inte har tillgång till den stora oeuvre av matematik som samlats genom historien. Men ibland briljerar datorer där människor är hopplösa. Berätta för en dator hur en lösning ser ut – ge den ett mål och ett väldefinierat sökutrymme – och sedan med rå kraft kan datorn hitta den. Fast det är en fråga om debatt om beräkningsresultat utgör meningsfulla tillägg till den matematiska kanonen. Den traditionella uppfattningen är att endast mänsklig kreativitet och intuition, via begrepp och idéer, utökar matematikens räckvidd, medan framsteg via datorer ofta avfärdas som ingenjörskonst.

Relaterad berättelse

Denna algoritm kan berätta vilka nummersekvenser en människa kommer att tycka är intressanta Resultatet antyder att maskiner en dag skulle kunna tränas för att upptäcka matematisk elegans och skönhet.

På sätt och vis är datorn och Collatz-förmodan en perfekt match. För det första, som Jeremy Avigad, en logiker och professor i filosofi vid Carnegie Mellon konstaterar, är idén om en iterativ algoritm grunden för datavetenskap - och Collatz-sekvenser är ett exempel på en iterativ algoritm, som går vidare steg-för-steg enligt till en deterministisk regel. På samma sätt är det ett vanligt problem inom datavetenskap att visa att en process avslutas. Datavetare vill i allmänhet veta att deras algoritmer slutar, det vill säga att de alltid returnerar ett svar, säger Avigad. Heule och hans medarbetare utnyttjar den tekniken för att tackla Collatz-förmodan, som egentligen bara är ett uppsägningsproblem.

Det fina med denna automatiserade metod är att du kan slå på datorn och vänta.

Jeffrey Lagarias

Heules expertis är med ett beräkningsverktyg som kallas en SAT-lösare – eller en tillfredsställbarhetslösare, ett datorprogram som avgör om det finns en lösning för en formel eller ett problem givet en uppsättning begränsningar. Även om det är avgörande, i fallet med en matematisk utmaning, behöver en SAT-lösare först problemet översatt, eller representerat, i termer som datorn förstår. Och som Yolcu, doktorand vid Heule, uttrycker det: Representation betyder mycket.

Ett långskott, men värt ett försök

När Heule först nämnde att han skulle tackla Collatz med en SAT-lösare, tänkte Aaronson: Det finns inget sätt i helvetet att detta kommer att fungera. Men han var lätt övertygad om att det var värt ett försök, eftersom Heule såg subtila sätt att förändra detta gamla problem som kunde göra det böjligt. Han hade märkt att en grupp av datavetare använde SAT-lösare för att framgångsrikt hitta avslutningsbevis för en abstrakt representation av beräkningar som kallas ett omskrivningssystem. Det var en longshot, men han föreslog för Aaronson att omvandling av Collatz-förmodan till ett omskrivningssystem skulle kunna göra det möjligt att få ett avslutningsbevis för Collatz (Aaronson hade tidigare hjälpt till att omvandla Riemann-hypotesen till ett beräkningssystem och kodade den i en liten Turing maskin). Den kvällen designade Aaronson systemet. Det var som en läxa, en rolig övning, säger han.

'I bokstavlig bemärkelse kämpade jag mot en Terminator - åtminstone en termineringssatsbevisare.'

Scott Aaronson

Aaronsons system fångade Collatz-problemet med 11 regler. Om forskarna kunde få ett avslutningsbevis för detta analoga system, genom att tillämpa de 11 reglerna i valfri ordning, skulle det bevisa att Collatz-förmodan var sann.

Heule försökte med toppmoderna verktyg för att bevisa uppsägningen av omskrivningssystem, vilket inte fungerade - det var en besvikelse om inte så överraskande. Dessa verktyg är optimerade för problem som kan lösas på en minut, medan alla metoder för att lösa Collatz förmodligen kräver dagar om inte år av beräkning, säger Heule. Detta gav motivation att finslipa sitt tillvägagångssätt och implementera sina egna verktyg för att omvandla omskrivningsproblemet till ett SAT-problem.

En representation av omskrivningssystemet med elva regler för Collatz-förmodan.

MARIN HEULE

Aaronson tänkte att det skulle vara mycket lättare att lösa systemet minus en av de 11 reglerna – att lämna ett Collatz-liknande system, ett lackmustest för det större målet. Han utfärdade en människa-mot-dator-utmaning: Den första som löser alla delsystem med 10 regler vinner. Aaronson försökte för hand. Heule prövad av SAT-lösare: Han kodade systemet som ett tillfredsställbarhetsproblem – med ytterligare ett smart lager av representation, och översatte systemet till datorns språkspråk av variabler som kan vara antingen 0:or och 1:or – och lät sedan sin SAT-lösare köra på kärnorna , söker efter bevis på uppsägning.

Systemet här följer Collatz-sekvensen för startvärdet 27—27 är längst upp till vänster i diagonalkaskaden, 1 är längst ner till höger. Det finns 71 steg, snarare än 111, eftersom forskarna använde en annan men likvärdig version av Collatz-algoritmen: om talet är jämnt, dividera med 2; annars multiplicera med 3, lägg till 1 och dividera sedan resultatet med 2.

MARIN HEULE

De lyckades båda bevisa att systemet slutar med de olika uppsättningarna av 10 regler. Ibland var det ett trivialt åtagande, för både människan och programmet. Heules automatiserade tillvägagångssätt tog högst 24 timmar. Aaronsons tillvägagångssätt krävde betydande intellektuell ansträngning, som tog några timmar eller till och med en dag – en uppsättning av 10 regler som han aldrig lyckades bevisa, även om han är övertygad om att han skulle kunna ha mer ansträngning. I en väldigt bokstavlig bemärkelse kämpade jag mot en Terminator, säger Aaronson - åtminstone ett termineringssatsbevis.

Yolcu har sedan dess finjusterat SAT-lösaren och kalibrerat verktyget för att bättre passa Collatz-problemets natur. Dessa trick gjorde hela skillnaden – att snabba upp avslutningsbevisen för delsystemen med 10 regler och minska körtiderna till bara sekunder.

Huvudfrågan som återstår, säger Aaronson, är: Hur är det med hela uppsättningen av 11? Du försöker köra systemet på hela setet och det körs bara för evigt, vilket kanske inte borde chockera oss, eftersom det är Collatz-problemet.

Som Heule ser det har den mesta forskningen inom automatiserat resonemang ett blindöga för problem som kräver mycket beräkning. Men baserat på sina tidigare genombrott tror han att dessa problem kan lösas. Andra har förvandlade Collatz har har skriva om systemet , men det är strategin att använda en finjusterad SAT-lösare i skala med formidabel beräkningskraft som kan få dragkraft mot ett bevis.

Hittills har Heule drivit Collatz-utredningen med hjälp av cirka 5 000 kärnor (processorenheterna som driver datorer; konsumentdatorer har fyra eller åtta kärnor). Som Amazon Scholar har han en öppen inbjudan från Amazon Web Services för att få tillgång till praktiskt taget obegränsade resurser – så många som en miljon kärnor. Men han är ovillig att använda betydligt mer.

Jag vill ha en indikation på att det här är ett realistiskt försök, säger han. Annars känner Heule att han skulle slösa med resurser och förtroende. Jag behöver inte 100% självförtroende, men jag skulle verkligen vilja ha några bevis för att det finns en rimlig chans att det kommer att lyckas.

Överladdar en förvandling

Det fina med denna automatiserade metod är att du kan slå på datorn och vänta, säger matematikern Jeffrey Lagarias, vid University of Michigan. Han har lekt med Collatz i ungefär femtio år och blivit kunskapens bevarare, sammanställt kommenterade bibliografier och redigerat en bok om ämnet, Den ultimata utmaningen. För Lagarias förde det automatiserade tillvägagångssättet att tänka på a 2013 tidning av Princeton-matematikern John Horton Conway, som funderade på att Collatz-problemet kan tillhöra en svårfångad klass av problem som är sanna och oavgörbara – men som på en gång inte bevisligen går att avgöra. Som Conway noterade: … det kan till och med vara så att påståendet att de inte är bevisbara inte i sig självt kan bevisas, och så vidare.

Om Conway har rätt, säger Lagarias, kommer det inte att finnas några bevis, automatiserade eller inte, och vi kommer aldrig att veta svaret.

Den människa som utan tvekan har kommit närmast är matematikern Terence Tao, vid University of California, Los Angeles. 2019 bevisade Tao att Collatz gissningar är det nästan sant för nästan alla siffror (förlitar sig nästan på två olika tekniska definitioner, inte desto mindre enligt den vanliga engelska betydelsen).

Tao tror att ett mänskligt bevis på gissningarna skulle vara mer matematiskt meningsfullt - att komma åt Varför av det - än ett datorbevis. Men att ha ett stort olöst problem som faller till en automatiserad prover kan överdriva en revolutionerande omvandling av hur matematiker använder datorhjälp i sitt arbete, säger han. Med ett så svårlöst problem som detta kommer vi att ta alla insikter vi kan få.

Vad Heule och hans medarbetare egentligen är ute efter är dock ett scenario som gör att datorn – med detta tillvägagångssätt, med detta problem – lyckas där människan misslyckas, eller vice versa. Vid det här laget vet vi inte om dessa tekniker är mycket starkare än vad människor kan göra för hand eller inte, eller om människor kan göra saker som datorn inte kan göra, säger Heule. Det vi vill veta är om människor eller datorer är bättre på att lösa sådana problem.

Låt oss därför se vem som löser Collatz-förmodan först.

Dölj