Määritelään funktio f:Z ->Z seuraavasti
f(x)=1, kun x=1
f(x)=f(x/2), kun x on parillinen
f(x)=f(3x 1), kun x on pariton ja x>1
Osoita, että tämä rekursiivinen määritelmä on todellakin funktio. Onko funktio primitiivirekursiivinen vai rekursiivinen?
f(x)=1, kun x=1
f(x)=f(x/2), kun x on parillinen
f(x)=f(3x 1), kun x on pariton ja x>1
Osoita, että tämä rekursiivinen määritelmä on todellakin funktio. Onko funktio primitiivirekursiivinen vai rekursiivinen?
Vastaukset 5
Vanhimmat
Selvästikin ainoa kyseeseen tuleva funktio on vakiofunktio f(x)=1. Joten se on primitiivirekursiivinen f(x)=Succ(Zero(x)).
Nyt jään innolla odottamaan miten Logistikko tai joku muu esittää todistuksen sille, että kyseessä on todellakin funktio. Ne eivät ole helppoja tehtäviä.
Kaikella todennäköisyydellä f(x) = 1, mutta kukaan ei ole sitä todistanut ja sitä ei voida siis olettaa todistuksessa:
http://en.wikipedia.org/wiki/Collatz_conjecture
mutta ei ainakaan näillä ehdoilla hyvin määritelty, ellei ensin todisteta Collatzin väittämää.
Nähdäkseni ainoa tapa todistaa, että näin voidaan määritellä funktio, on todistaa ensin Collatzin konjektuuri: Ts. on todistettava, että jollakin tavalla päädytään aina siihen x:n arvoon, jolla f:n arvo on eksplisiittisesti annettu, ts. x:n arvoon 1.
Jos Collatzin konjektuuri ei pidä paikkaansa, niin Collatzin jonoista löytyy joko ei-triviaaleja syklejä (ts. syklejä, jotka eivät sisällä lukua yksi) tai sitten lukujono, joka huitelee äärettömyyksiin (tai molemmat). Molemmissa tapauksissa voidaan f:lle valita arvoja, jotka poikkeavat f(1):lle määritellystä arvosta 1. Ensimmäisessä tapauksessa voidaan jokaisen erillisen syklin luvuille f:n arvo valita toisista sykleistä ja myös f(1):stä (triviaali sykli) riippumatta . Jälkimmäisessä sama pätee äärettömiin huitelevan lukujonon luvuille.
Itse olen osoittanut, että jos Collatzin jono sisältää ei-triviaaleja syklejä, niin näiden syklien sisältämien lukujen lukumäärä on vähintään miljardi eri lukua. Yleisesti ottaen Collatzin väittämää ei kuitenkaan ainakaan toistaiseksi ole tietääkseni todistettu.
Matti K. Sinisalo
"mutta ei ainakaan näillä ehdoilla hyvin määritelty, ellei ensin todisteta Collatzin väittämää."
Ilmeisestikin Collatzin väittämästä seuraa vastaus esitettyyn kysymykseen, mutta mahtaako päteä toisin päin?
Alkuperäiseltä voisi kysyä, että mistä tämä tehtävä on peräisin?
Ja sitten heräsin, eli ei mitään :)