matematikk.net

Gitt en hvilkensomhelst tekst i det norske alfabetet, inkludert tall, mellomrom, komma, punktum, kolon, bindestrek - lag en bijektiv funksjon (altså en invertibel funksjon) som tar teksten og returnerer et unikt heltall.

Korollar: Heltallene inneholder alle bøker som noensinne vil bli skrevet.

Ekstraspørsmål: Hvor stort vil dette tallet være i verst mulig tilfelle, dersom du skulle kode dette innlegget?

Ekstraspørsmål 2: Lag en funksjon som gir deg intervallet du må søke i for å finne en tekst av lengde n. Det er greit om funksjonen er en tilnærming, men tilnærmingen bør bli bedre og bedre for store n.

Ekstraspørsmål for de med datamaskin: Restriher funksjonen over til bare å kode for bokstaver i det norske alfabetet. Hvor mange n<1000000 koder for reelle norske ord?

Siden det er [tex]29[/tex] bokstaver, [tex]10[/tex] siffer og [tex]5[/tex] tegn blir det [tex]44[/tex] forskjellige elementer vi kan bruke i enhver plassering i teksten. Dvs i en tekst med [tex]N[/tex] elementer er det [tex]44^N[/tex] forskjellige tekster som kan lages. Vi kan nummerere enhver tekst med [tex]N[/tex] elementer med et tall mellom [tex]1[/tex] og [tex]44^N[/tex].

Vi definerer [tex]f(k)=\sum^{N-1}_{i=1}44^i + k[/tex] og lar [tex]f[/tex] mappe en tekst vi har nummerert [tex]k[/tex] til [tex]f(k)=\frac{44^N-44}{43}+k[/tex]. Dette er en bijeksjon siden vi kan lage blokker av etterfølgende sekvenser av tall med størrelser [tex]44,44^2,44^3...[/tex] hvor tallet i blokk nr [tex]t[/tex] vil ha [tex]t[/tex] elementer, og posisjonen i blokken unikt definerer rekkefølgen av elementene.


Vi kan lage en algoritme for nummerering av en tekst med [tex]N[/tex] elementer:
Hvis vi merker hvert element med et heltall mellom (og inkludert) [tex]0[/tex] og [tex]43[/tex] så vil f.eks tallet [tex]1,23,42[/tex] i [tex]44[/tex] tallsystemet representere en unik tekst med tre elementer. Vi definerer da [tex]k[/tex] som dette tallet i [tex]10[/tex]-tallsystemet.

For det verste utfallet:

Vi lar den første bokstaven g være nummerert med [tex]43[/tex], den andre, i, være nummerert med [tex]42[/tex] osv.. (Vi hopper over der elementet gjentar seg til vi har nummerert alle de [tex]44[/tex] forskjellige elementene) Da vil tekstens nummerering (I [tex]44[/tex] tallsystemet) være [tex]k=43,42,41,41,...,0,a_{N-45},a_{N-44},...,a_{1}[/tex] hvor [tex]a_i[/tex] er verdien til tallet som element nr. [tex]i[/tex] måtte ha. Da vil den største mulige verdien til teksten være [tex]f(k)[/tex].

For å finne intervallet kan vi første velge [tex]I=44 \lfloor \frac{f(k)}{44} \rfloor[/tex] som er verdien til teksten av første nummerering i sin klasse av antall elementer. [tex]I[/tex] vil da ha formen [tex]\frac{44^n-44}{43}[/tex] hvor [tex]n[/tex] er antall elementer i teksten nummerert som [tex]f(k)[/tex].

Da får vi at

[tex]n=\frac{\ln(43I+44)}{\ln(44)}=\frac{\ln(43 \cdot 44 \lfloor \frac{f(k)}{44} \rfloor+44)}{\ln(44)}[/tex]

Jepp, flott, det er en godt brukbar metode. En annen mulighet er å mappe n'te symbol i teksten til n'te primtal, og la multiplisiteten til primtallet være tallet som korresponderer med symbolet (multiplisitet 1 er a). På den måten blir f.eks.

[tex]f( \text{daofeishi} ) = 2^4 3^1 5^{15} 7^6 11^5 13^9 17^{19} 19^8 23^9 = 2152494136175287722734777458354829584482230827302891727944835167294433593750000[/tex]

Fin den! Er det dette som kalles Gödel-nummerering?

Dette gir i midlertidig ikke en bijeksjon med de naturlige tallene som ko-domene forresten, eller var det ikke det du spurte om? Dessuten er jeg veldig interessert i svaret ditt på den neste siste oppgaven!

Jepp, dette er Gödels triks. Og nei, det har du selvsagt rett i - det er ikke en bijeksjon med N, og jeg mente egentlig å skrive bijektiv med en undermengde av N. Men hei, din løsning tok seg av skrivefeilen min . Apropos neste: http://en.wikipedia.org/wiki/Primorial .

Dette med gödelnummerering har selvfølgelig applikasjoner langt, langt utenfor dette med alfabeter. Det er derfor "logic 144" teller både som matematikk- og filosofikurs her Hvis du er interessert kan jeg sende over kursnotatene.