3n + 1

Et velkendt problem på grænsefladen mellem talteori og algoritmeteori er Collatz’ formodning. Det skyldes den tyske matematiker Lothar Collatz, stammer fra 1937 og er meget nemt at forklare:

Vælg et naturligt tal n som x_0.

Sæt nu x_{i+1} = 3n+1 hvis n er ulige og x_{i+1} = n/2 hvis n er lige.

På denne måde får vi en følge af værdier x_0, x_1, x_2, \ldots. Det er ikke svært at se, at hvis x_k = 1, vil følgen fra da af være periodisk med elementerne 1,4,2,1,4,2,\ldots. Det er meget nemt at skrive et lille program, der beregner værdierne i følgen, og det viser sig hurtigt, at med alle de startværdier man kan komme i tanke om, ender vi på et tidspunkt med værdien 1. Hvis det er ved x_k, vi når til 1 første gang, kalder vi k for følgens længde.

På grafen ovenfor kan man se følgens længde som funktion af startværdien for mindre værdier af denne.

Men gælder det virkelig altid at en følge har en længde? Dvs. når vi altid frem til 1 til sidst? Collatz’ formodning er, at det altid er tilfældet. I matematik er det som bekendt ikke nok med anekdotisk evidensgrundlag; der skal et generelt argument til. Den tyske matematiker Gerhard Opfer, som i sin tid havde Collatz som vejleder, har i år hævdet at have bevist Collatz’ formodning, men han har for nylig måttet trække sin påstand tilbage. Et lidt kynisk argument for at der måtte være en fejl er, at et påstået bevis på kun 11 sider næppe kan være korrekt! Paul Erdös sagde i sin tid, at matematikken endnu ikke er rede til at kunne levere et bevis – og tilbød 500 dollars i præmie til den, der kunne.

Men er Collatz’ formodning overhovedet vigtig? Som i så mange andre tilfælde er svaret, at det afhænger af definition af vigtighed. I en grundforskningssammenhæng er svaret et ubetinget ja, for som det er tilfældet for så mange andre åbne problemer i de matematiske fag, har arbejdet med Collatz’ formodning kastet en masse interessante matematiske opdagelser af sig. På Wikipedias udmærkede side om Collatz’ formodning kan man læse meget mere om disse.

F.eks. viste Kurtz og Simon i 2007, at man kan generalisere problemet til såkaldte Collatz-funktioner og bevise, at det er uafgørbart om en given Collatz-funktion og en given startværdi vil give en følge, der ender i 1. Beviset bygger på en generalisation af et resultat af John Conway, der kun kan håndtere startværdier på formen 2^k. Det spændende ved sådanne beviser for uafgørbarhed er, synes jeg, at de afslører at et begrebsapparat er “tilpas interessant”.

Kurtz og Simons resultat siger ikke noget om Collatz’ formodning. Formodningen handler ikke om afgørbarhed, og selve formodningen er trivielt afgør – den er jo enten sand eller falsk. Hvad der så faktisk er tilfældet, ved vi derimod ikke.

(Visited 99 times, 1 visits today)
Loading Facebook Comments ...

Skriv et svar