Väänäsen matemaattinen logiikka-kirjassa pyydetään harjoitustehtävänä osoittaa, että seuraava funktio f:N->{0,1} on primitiivirekursiivinen
f(n)=1, jos irrationaaliluvun Pii desimaaliesityksessä esiintyy vähintään n kpl peräkkäin numeroa 5
f(n)=0, muutoin
Tässä voi varmaan olettaa, että funktio
g:N->{0,..,9}
g(n)=Pii:n n.s desimaali.
on primitiivirekursiivinen.
Mutta jos tarkemmin katselee funktiota f, niin eihän se voi olla primitiivirekursiivinen, koska emme tiedä kuinka pitkälle Piin desimaaleja on laskettava kunnes löytyy n kpl 5:sia vai löytyykö koskaan. Näin siis ainakin toistaiseksi, ei tunneta vielä Piin ominaisuuksia. Jos taas tiedettäisiin, että Pii on esim. normaaliluku kannassa 10, niin f(n)=1 kaikilla n. Lähes 100% voimme sanoa, että näin on mutta, mutta..
Onko tässä funktiossa f, jotain miten se voidaan näyttää primitiivirekursiiviseksi vai onko tehtävän anto kirjassa väärin?
f(n)=1, jos irrationaaliluvun Pii desimaaliesityksessä esiintyy vähintään n kpl peräkkäin numeroa 5
f(n)=0, muutoin
Tässä voi varmaan olettaa, että funktio
g:N->{0,..,9}
g(n)=Pii:n n.s desimaali.
on primitiivirekursiivinen.
Mutta jos tarkemmin katselee funktiota f, niin eihän se voi olla primitiivirekursiivinen, koska emme tiedä kuinka pitkälle Piin desimaaleja on laskettava kunnes löytyy n kpl 5:sia vai löytyykö koskaan. Näin siis ainakin toistaiseksi, ei tunneta vielä Piin ominaisuuksia. Jos taas tiedettäisiin, että Pii on esim. normaaliluku kannassa 10, niin f(n)=1 kaikilla n. Lähes 100% voimme sanoa, että näin on mutta, mutta..
Onko tässä funktiossa f, jotain miten se voidaan näyttää primitiivirekursiiviseksi vai onko tehtävän anto kirjassa väärin?
Vastaukset 2
Vanhimmat
Primitiivirekursiivinen funktio on sellainen funktio jolle voimme määritä laskentavaatimuksen, esim. ohjelma joka ratkaisee kauppamatkustajan ongelman on primitiivirekursiivinen sillä tiedämme, että mikäli kaupunkeja on n kpl, niin n! kokeilun jälkeen löydämme vastauksen varmasti.
Rekursiivinen, joka ei-primitiivinen on sellainen, että emme tiedä laskenta-aikaa, mutta tiedämme pysähtyykö ohjelma. Esim. Ackermanin funktio. Se voidaasn kaikilla syötteillä laskea, mutta ajan arvioiminen on mahdotonta, aika vaatimus kasvaa "hirviömäisesti".
Sitten funktioita, jotka voidaan määrittää, mutta emme pysty selvittämään pysähtyykö ne koskaan.
Funktiostasi f ei voida sanoa varmuudella mitään, kunnes luvun Pi ne ominaisuudet, jotka ovat selvitettävissä ovat tiedossa. Primitiivirekursiivinen se ei välttämättä ole. Rekursiivinen lähes varmasti.
Jos funktiosi on rekursiivinen on se primitiivirekursiivinenkin, sillä kyseessähän on vakio funktio f(n)=1.
Jos taas ohjelma saattaa jäädä ikuisesti etsimään vastausta, niin se ei ole rekursiivinen.
Luku Pii tuskin on niin "epäsäännöllinen" että ohjelma ei löytyisi joka antaa vastauksen.