Er computere klar til at løse dette notorisk uhåndterlige matematikproblem?

Fru Tech | SuperRembo via codingtrain

Datalogen Marijn Heule er altid på udkig efter en god matematisk udfordring. Heule, som er lektor ved Carnegie Mellon University, har et imponerende ry for at løse vanskelige matematiske problemer med beregningsværktøjer. Hans resultat i 2016 med det boolske pythagoreiske tripleproblem var et enormt overskriftsfangende bevis: To hundrede terabyte matematisk bevis er det største nogensinde . Nu implementerer han en automatiseret tilgang til at angribe den forbløffende simple Collatz-formodning.

Først foreslået (ifølge nogle beretninger) i 1930'erne af den tyske matematiker Lothar Collatz, giver dette talteoretiske problem en opskrift eller algoritme til at generere en numerisk rækkefølge : Start med ethvert positivt heltal. Hvis tallet er lige, divideres med to. Hvis tallet er ulige, skal du gange med tre og tilføje en. Og så gør det samme, igen og igen. Formodningen hævder, at sekvensen altid vil ende på 1 (og derefter løbende cykle gennem 4, 2, 1).

Tallet 5 genererer for eksempel kun seks led:

5, 16, 8, 4, 2, 1

Tallet 27 cykler gennem 111 led, oscillerende op og ned - når dets højde når 9.232 - før det til sidst lander på 1.

Tallet 40 genererer en anden kort sekvens:

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

Til dato er formodningen blevet kontrolleret af computer for alle startværdier op til næsten 300 milliarder milliarder, og hvert tal når til sidst 1.

De fleste forskere mener, at formodningen er sand. Det har lokket masser af matematikere og ikke-matematikere, men ingen har fremlagt et bevis. I begyndelsen af ​​1980'erne erklærede den ungarske matematiker Paul Erdős: Matematik er endnu ikke klar til sådanne problemer.

Det, vi gerne vil vide, er, om mennesker eller computere er bedre til at løse sådanne problemer.

Marijn Heule

Og han har nok ret, siger Heule. For Heule er Collatz' tiltrækning ikke så meget udsigten til et gennembrud, som det er at fremme automatiserede ræsonnementteknikker. Efter at have puslet med det i fem år, udsendte Heule og hans samarbejdspartnere, Scott Aaronson og Emre Yolcu, for nylig en papir på arXiv preprint-serveren. Selvom det ikke lykkes os at bevise Collatz-formodningen, skriver de, mener vi, at ideerne her repræsenterer en interessant ny tilgang.

Det er en nobel fiasko, siger Aaronson, en datalog ved University of Texas i Austin. En fiasko, fordi de ikke beviste formodningen. Noble, fordi de gjorde fremskridt i en anden forstand: Heule ser det som et udgangspunkt for at afgøre, om mennesker eller computere er bedre til at bevise sådanne problemer.

Oversættelse af matematik til beregning

For mange matematikproblemer er computere håbløse, da de ikke har adgang til det enorme oeuvre af matematik, der er opsamlet gennem historien. Men nogle gange udmærker computere sig, hvor mennesker er håbløse. Fortæl en computer, hvordan en løsning ser ud – giv den et mål og et veldefineret søgeområde – og så kan computeren finde den med brute force. Selvom det er et spørgsmål om debat om beregningsresultater udgør meningsfulde tilføjelser til den matematiske kanon. Den traditionelle opfattelse er, at kun menneskelig kreativitet og intuition, via begreber og ideer, udvider matematikkens rækkevidde, hvorimod fremskridt via computer ofte afvises som teknik.

Relateret historie

Denne algoritme kan fortælle, hvilke talsekvenser et menneske vil finde interessante Resultatet antyder, at maskiner en dag kunne blive trænet til at spotte matematisk elegance og skønhed.

På en måde er computeren og Collatz-formodningen et perfekt match. For det første, som Jeremy Avigad, en logiker og professor i filosofi ved Carnegie Mellon bemærker, er idéen om en iterativ algoritme grundlaget for datalogi - og Collatz-sekvenser er et eksempel på en iterativ algoritme, der fortsætter trin-for-trin ifølge til en deterministisk regel. På samme måde er det et almindeligt problem inden for datalogi at vise, at en proces afsluttes. Dataloger vil generelt gerne vide, at deres algoritmer ophører, hvilket vil sige, at de altid returnerer et svar, siger Avigad. Heule og hans samarbejdspartnere udnytter denne teknologi til at tackle Collatz-formodningen, som egentlig bare er et opsigelsesproblem.

Skønheden ved denne automatiserede metode er, at du kan tænde for computeren og vente.

Jeffrey Lagarias

Heules ekspertise er med et beregningsværktøj kaldet en SAT-løser - eller en tilfredsstillelsesløser, et computerprogram, der bestemmer, om der er en løsning på en formel eller et problem givet et sæt begrænsninger. Selvom det er afgørende, i tilfælde af en matematisk udfordring, skal en SAT-løser først have problemet oversat eller repræsenteret i vendinger, som computeren forstår. Og som Yolcu, ph.d.-studerende ved Heule, udtrykker det: Repræsentation betyder meget.

Et langskud, men et forsøg værd

Da Heule første gang nævnte at tackle Collatz med en SAT-løser, tænkte Aaronson: Der er ingen måde i helvede, at dette kommer til at fungere. Men han var let overbevist om, at det var et forsøg værd, da Heule så subtile måder at transformere dette gamle problem på, som kunne gøre det bøjeligt. Han havde bemærket, at et fællesskab af dataloger brugte SAT-løsere til at finde termineringsbeviser for en abstrakt repræsentation af beregninger kaldet et omskrivningssystem. Det var et longshot, men han foreslog Aaronson, at transformation af Collatz-formodningen til et omskrivningssystem kunne gøre det muligt at få et termineringsbevis for Collatz (Aaronson havde tidligere hjulpet med at transformere Riemann-hypotesen til et beregningssystem ved at indkode den i en lille Turing maskine). Den aften designede Aaronson systemet. Det var ligesom en lektieopgave, en sjov øvelse, siger han.

'I en meget bogstavelig forstand kæmpede jeg mod en Terminator - i det mindste en termineringssætningsbevis.'

Scott Aaronson

Aaronsons system fangede Collatz-problemet med 11 regler. Hvis forskerne kunne få et afslutningsbevis for dette analoge system, ved at anvende de 11 regler i en hvilken som helst rækkefølge, ville det bevise, at Collatz-formodningen er sand.

Heule prøvede med state-of-the-art værktøjer til at bevise afslutningen af ​​omskrivningssystemer, hvilket ikke virkede - det var skuffende, hvis ikke så overraskende. Disse værktøjer er optimeret til problemer, der kan løses på et minut, mens enhver tilgang til løsning af Collatz sandsynligvis kræver dage, hvis ikke års beregning, siger Heule. Dette gav motivation til at finpudse deres tilgang og implementere deres egne værktøjer til at transformere omskrivningsproblemet til et SAT-problem.

En repræsentation af omskrivningssystemet med 11 regler for Collatz-formodningen.

MARINE HEULE

Aaronson regnede med, at det ville være meget nemmere at løse systemet minus en af ​​de 11 regler - at efterlade et Collatz-lignende system, en lakmusprøve for det større mål. Han udstedte en menneske-versus-computer-udfordring: Den første, der løser alle undersystemer med 10 regler, vinder. Aaronson prøvede i hånden. Heule prøvet af SAT-løser: Han kodede systemet som et tilfredsstillelsesproblem – med endnu et smart lag af repræsentation, der oversatte systemet til computerens sprog af variabler, der kan være enten 0'er og 1'er – og lod derefter sin SAT-løser køre på kernerne , søger efter bevis for opsigelse.

Systemet her følger Collatz-sekvensen for startværdien 27—27 er øverst til venstre i den diagonale kaskade, 1 er nederst til højre. Der er 71 trin i stedet for 111, da forskerne brugte en anden, men ækvivalent version af Collatz-algoritmen: hvis tallet er lige, så divider med 2; ellers gange med 3, add 1, og divider derefter resultatet med 2.

MARINE HEULE

Det lykkedes dem begge at bevise, at systemet afsluttes med de forskellige sæt af 10 regler. Nogle gange var det et trivielt foretagende, for både mennesket og programmet. Heules automatiserede tilgang tog højst 24 timer. Aaronsons tilgang krævede en betydelig intellektuel indsats, som tog et par timer eller endda en dag – et sæt på 10 regler, han aldrig formåede at bevise, selvom han er overbevist om, at han kunne få det med mere indsats. I en meget bogstavelig forstand kæmpede jeg mod en Terminator, siger Aaronson - i det mindste en termineringssætningsbevis.

Yolcu har siden finjusteret SAT-løseren og kalibreret værktøjet, så det bedre passer til Collatz-problemets natur. Disse tricks gjorde hele forskellen - at fremskynde afslutningsbeviserne for 10-regel-undersystemerne og reducere kørselstiderne til få sekunder.

Det vigtigste spørgsmål, der er tilbage, siger Aaronson, er: Hvad med det fulde sæt af 11? Du prøver at køre systemet på det fulde sæt, og det kører bare for evigt, hvilket måske ikke burde chokere os, for det er Collatz-problemet.

Som Heule ser det, har det meste af forskningen i automatiseret ræsonnement et blindt øje for problemer, der kræver masser af beregning. Men baseret på hans tidligere gennembrud mener han, at disse problemer kan løses. Andre har forvandlet Collatz har har omskrive system , men det er strategien med at bruge en finjusteret SAT-løser i skala med formidabel regnekraft, der kan vinde trækkraft mod et bevis.

Hidtil har Heule kørt Collatz-undersøgelsen ved hjælp af omkring 5.000 kerner (behandlingsenhederne, der driver computere; forbrugercomputere har fire eller otte kerner). Som Amazon Scholar har han en åben invitation fra Amazon Web Services til at få adgang til praktisk talt ubegrænsede ressourcer - så mange som en million kerner. Men han er tilbageholdende med at bruge væsentligt mere.

Jeg vil gerne have noget indikation af, at det er et realistisk forsøg, siger han. Ellers føler Heule, at han ville spilde ressourcer og tillid. Jeg har ikke brug for 100 % selvtillid, men jeg vil virkelig gerne have noget bevis på, at der er en rimelig chance for, at det lykkes.

Supercharger en transformation

Skønheden ved denne automatiserede metode er, at du kan tænde for computeren og vente, siger matematikeren Jeffrey Lagarias fra University of Michigan. Han har leget med Collatz i omkring halvtreds år og blevet vogter af viden, kompilerede kommenterede bibliografier og redigerede en bog om emnet, Den ultimative udfordring. For Lagarias mindede den automatiserede tilgang om en 2013 papir af Princeton-matematikeren John Horton Conway, der tænkte over, at Collatz-problemet måske er blandt en undvigende klasse af problemer, der er sande og uafklarelige - men på én gang ikke beviseligt uafklarelige. Som Conway bemærkede: … det kan endda være, at påstanden om, at de ikke kan bevises, ikke i sig selv kan bevises, og så videre.

Hvis Conway har ret, siger Lagarias, vil der ikke være noget bevis, automatiseret eller ej, og vi vil aldrig kende svaret.

Det menneske, der uden tvivl er kommet tættest på, er matematikeren Terence Tao, ved University of California, Los Angeles. I 2019 beviste Tao, at Collatz-formodningen er næsten sandt for næsten alle tal (afhænger næsten af ​​to forskellige tekniske definitioner, ikke desto mindre i overensstemmelse med den almindelige engelske betydning).

Tao mener, at et menneskeligt bevis på formodningen ville være mere matematisk meningsfuldt - at komme til hvorfor af det - end et computerbevis. Men at få et stort uløst problem til at falde til en automatiseret bevis kan supercharge en revolutionær transformation i, hvordan matematikere bruger computerassistance i deres arbejde, siger han. Med et problem så vanskeligt som dette, vil vi tage den indsigt, vi kan få.

Det, Heule og hans samarbejdspartnere i virkeligheden er ude efter, er imidlertid et scenarie sådan, at computeren – ved hjælp af denne tilgang med dette problem – lykkes, hvor mennesket svigter, eller omvendt. På nuværende tidspunkt ved vi ikke, om disse teknikker er meget stærkere, end hvad mennesker kan gøre i hånden eller ej, eller om mennesker kan gøre ting, som computeren ikke kan, siger Heule. Det, vi gerne vil vide, er, om mennesker eller computere er bedre til at løse sådanne problemer.

Til det formål, lad os se, hvem der først løser Collatz-formodningen.

skjule