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?
Gödel klarte det, klarer du?
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
(稻飞虱)
For en fri matematikk! The Declaration of Linear Independence
For en fri matematikk! The Declaration of Linear Independence
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.
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.
Sist redigert av Charlatan den 22/02-2009 02:56, redigert 3 ganger totalt.
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].
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].
Sist redigert av Charlatan den 22/02-2009 02:54, redigert 2 ganger totalt.
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]
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]
[tex]f( \text{daofeishi} ) = 2^4 3^1 5^{15} 7^6 11^5 13^9 17^{19} 19^8 23^9 = 2152494136175287722734777458354829584482230827302891727944835167294433593750000[/tex]
Sist redigert av daofeishi den 22/02-2009 03:38, redigert 4 ganger totalt.
(稻飞虱)
For en fri matematikk! The Declaration of Linear Independence
For en fri matematikk! The Declaration of Linear Independence
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!
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!
Sist redigert av Charlatan den 22/02-2009 03:28, redigert 1 gang totalt.
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.
. 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.(稻飞虱)
For en fri matematikk! The Declaration of Linear Independence
For en fri matematikk! The Declaration of Linear Independence