"Det är synd att 99 % av
journalisterna skall fördärva
förtroendet för en hel yrkeskår"
(okänd)

"Ormar äro älskliga varelser,
om man råkar tillhöra samma
giftgrupp"
(Artur Lundkvist)

"Ju längre ett samhälle
kommer från sanningen,
desto mer kommer detta
samhälle att hata dem
som säger sanningen"
(George Orwell)

"Den som gifter sig med
tidsandan blir snabbt änka."
(Goethe)

"Civiliserade är de kulturer
och individer som respekterar
andra."
(hört på Axesskanalen)

"Det tragiska med vanligt
sunt förnuft är att det
inte är så vanligt."
(Albert Einstein)

"Halv kristendom tolereras
men föraktas.
Hel kristendom respekteras
men förföljs."
(Okänd)

"För att komma till flodens
källa måste man simma
mot strömmen."
(Stanislaw Jerzy Lec)

"Jag noterar att alla de
människor, som är för
abort, redan är födda."
(Ronald Reagan)

Senast ändrad: 2007 01 17 17:52

Algoritmisk komprimerbarhet

Ett rationellt tal är ett tal som utgör kvoten av två heltal, t ex 2/7, 5/1 eller 153/73. Då vissa rationella tal decimalutvecklas erhålls heltal eller ändliga decimalbråk. 25/5 blir t ex 5 och 1/4 blir 0,25. En ytterligare möjlighet är att man får s k periodiska decimalbråk. Sådana bråk har ett oändligt antal decimaler, bestående av ett begränsat antal siffror (perioden) som upprepas regelbundet. Några exempel är:

ALGORITMISK00.jpg    Perioden är i detta fall 3 (består av en siffra som upprepas)

 

ALGORITMISK01.jpg    Här är perioden lika med 18 (två siffror upprepas).

 

ALGORITMISK02.jpg    I detta fall består perioden av 6 siffror.

 

Ovanstående oändliga decimalbråk kan fullständigt beskrivas genom att endast perioden anges. Man brukar sägas att bråk av denna typ är algoritmiskt komprimerbara. I dessa fall kan ett oändligt antal siffror komprimeras till ett begränsat uttryck, vilket innehåller lika mycket information som hela den oändliga sifferföljden. Många tal ges emellertid av decimalföljder, vilka inte är komprimerbara. Tal av denna typ är t ex π =3,141592653589793238462643... och ALGORITMISK03.jpg Dylika tal kan inte representeras i någon förkortad form. Enda sättet att exakt beskriva talet π är genom att antingen skriva symbolen π eller också skriva ut hela decimalutvecklingen. Det senare är naturligtvis i praktiken omöjligt.

Ett annat exempel på algoritmisk komprimerbarhet finner vi om vi betraktar talföljder. Följden av de udda talen 1, 3, 5, 7, 9, 11, ... kan t ex sammanfattas i formeln 2n + 1, där n = 0, 1, 2, 3, ... På liknande sätt kan många andra talföljder komprimeras till enkla formler. Givetvis existerar det också talföljder vilka, precis som π, inte går att komprimera. Ett exempel på detta är följden av de s k primtalen 1, 2, 3, 5, 7, 11, 13,... (primtalen är de tal som endast är delbara med sig själva och med ett). Det existerar ingen känd formel med vars hjälp man kan generera alla primtal, varför en fullständig lista med alla primtal består av en fullständig lista med alla primtal.

Algoritmisk komprimerbarhet illustrerar på ett mycket bra sätt hur vetenskapen fungerar. All naturvetenskap utgår från att den fysiska verkligheten går att sammanfatta i korta formler. Ett exempel på detta är Keplers välkända lagar för planetbanorna. Den danske astronomen Tycho Brahe hade under flera decennier observerat rörelsen hos de 5 ljusstarkaste planeterna. Resultaten testamenterade han till sin lärjunge Johannes Kepler. Vad Kepler fann, var att Tycho Brahes i det närmaste ändlösa tabeller av planetobservationer kunde komprimeras till tre enkla lagar. På liknande sätt upptäckte Isaac Newton att alla mätningar på mekaniska system kunde komprimeras till tre, eller om man inkluderar gravitationen, fyra enkla lagar, vilka innehåller exakt samma information som summan av alla dessa mätningar. Om verkligheten inte vore algoritmiskt komprimerbar, skulle forskarna reduceras till ett slags bibliotekarier eller bokhållare, som vore begränsade till att föra oändliga listor av mätresultat utan hopp om att någonsin kunna koncentrera dessa mätdata i kortare form (det vi kallar naturlagar är helt enkelt dessa komprimerade mätdata).

Tillbaka till Vetenskap och tro.

Du kan läsa mer om vetenskap och tro i: Fakta och teori

© Krister Renard