Gödeltal är en metod som bland annat kan användas för att koda strängar till ett naturligt tal. Talet blir ofta oerhört stort, och redan en kort mening kan generera ett tal större än en googol. Det går att avkoda gödeltal, men att faktorisera dessa enorma tal kan bli en oöverstiglig uppgift för även den snabbaste dator. Däremot skulle en sk kvantdator klara det på rimlig tid.
Kodningen går till så att man översätter tecken för tecken med ett numeriskt värde, som man sedan höjer konsekutiva primtal (2,3,5,7,11,13…) med. Sedan multipliceras resultaten. Om vi använder talvärdena för bokstäverna (dvs A=1, B=2, C=3…) blir det gödeltal som motsvarar ordet ”lukas” nästan en septiljon.
212*321*511*71*1119 ≈ 8,96*1041
Begreppet förekommer i Peter Nilsons bok Rymdväktaren & Projekt Nyaga. Dock förklaras det felaktigt så att man istället har talvärdena som bas och primtalen som exponent. Gödelfunktionen av ”lukas” blir då istället 122*213*115*17*1911 ≈ 2,5*1025. I övrigt är det en mycket bra bok som jag varmt kan rekommendera till alla som vill ha spännande science fiction som respekterar naturlagarna.
1 kommentar:
Det är ingen svår uppgift att avkoda gödeltal och det behövs absolut ingen kvantdator för att göra det.
Primtalsfaktorerna i gödeltalen är små och dessutom kända, så det enda man behöver göra är vanlig heltalsdivision. Ett enkelt problem för en vanlig skrivbordsdator.
Den alternativa "gödelkodningen" som du visar längst ner fungerar inte, eftersom man inte kan skilja på t.ex 2^3*2^7 och 8^5 (båda ger 1024 som resultat.)
Skicka en kommentar