Operaatori μx(n 1) abil (*)-arvutatavatest funktsioonidest saadud funktsioonide (*)-arvutatavus (0)

Operaatori
abil (*)-arvutatavatest funktsioonidest saadud funktsioonide (*)-arvutatavus
Tallinn 2014

Sissejuhatus

Käesolevas referaadis keskendume operaatori
abil saadud funktsioonide (*)-arvutatavusele, need funktsioonid on osaliselt rekursiivsed. Selleks, et uurida selliseid protsesse toome sisse vajalikud mõisted ja definitsioonid ning tõestame lemma , mis tõestab, et (*)-arvutatavatest funktsioonidest operaatori
abil saadud funktsioonid on samuti (*)-arvutatavad. Anname ka sellise teoreemi tõestamise idee, mis ütleb, et iga osaliselt rekursiivne funktsioon on Turingi mõttes arvutatav ehk antud juhul (*)-arvutatav.

1. Osaliselt rekursiivsed funktsioonid. Operaatori µ abil saadud funktsioonide (*)-arvutatavus.

Enne põhiosa juurde asumist toome sisse mõned vajalikud definitsioonid.
Definitsioon 1.1. ([1], 9) Algfunktsioonideks nimetatakse järgmisi naturaalarvulisi funktsioone:
Funktsioone
nimetatakse valikufunktsioonideks.
Definitsioon 1.2. ([1], 10) Funktsioon
on avaldatud funktsioonide
ja
kaudu asendusskeemi abil, kui
Definitsioon 1.3. ([1], 10) Funktsioon
on avaldatud funktsioonide
ja
(konstandi
ja funktsiooni ) kaudu lihtrekursiooniskeemi abil, kui
juhul
või
Definitsioon 1.4. ([1], 22) Olgu funktsioon
määratud hulga
mingil alamhulgal ja olgu . Kirjutame
ja ütleme, et funktsioon
on avaldatud funktsiooni
kaudu, rakendades argumendile
- operaatorit , kui
Funktsiooni
võib arvutada järgmise algoritmi järgi:
Arvutame järjestikku
................................................
Kui saame mingi arvu
korral, , siis lõpetame ja väljastame .
Definitsioon 1.5. ([1], 23) Funktsiooni
nimetatakse osaliselt rekursiivseks (ORF), kui ta on algfunktsioon või teda saab avaldada algfunktsioonide kaudu, kasutades lõplik arv kordi asendusskeemi, lihtrekursiooniskeemi ja -operaatorit.
Mõiste funktsiooni (*)-arvutatavus tähendab seda, et selle funktsiooni väärtusi on võimalik arvutada vastava Turingi masina abil, kus see „(*)“ märgib kahte tingimust, mis peavad kehtima vastava Turingi masina korral. Need tingimused on järgmised:
1*) funktsiooni väärtuse arvutamisel ei asu masina lugev-kirjutav pea lindil kunagi vasakul pool argumendi (argumentide) esimest vasakpoolset pesa,
2*) kui funktsiooni väärtus antud argumentidel pole määratud, siis masin ei peatu.
Edasi uurime, kas (*)-arvutatavatest funktsioonidest operaatori
abil saadud funktsioonid on ka (*)-arvutatavad. Need funktsioonid, millega me tegeleme, on kõik osaliselt rekursiivsed funktsioonid ja neil on
argumenti. Seetõttu järgmise teoreemiga:
Teoreem . ([1], 24) Iga osaliselt rekursiivne funktsioon on arvutatav Turingi mõttes.
See, et funktsioon on arvutatav Turingi mõttes, tähendabki antud juhul, et see funktsioon on (*)-arvutatav.
Tõestuse idee. See teoreem tõestatakse induktsiooniga osaliselt rekursiivse funktsiooni definitsiooni järgi, s.t. näidatakse, et
1) iga algfunktsioon on arvutatav,
2) kui defineerime skeemide abil uusi funktsioone, siis arvutatavus kandub edasi.
Antud teoreemi sees on vaja tõestada järgmised lemmad:
Lemma 1. ([1], 25) Algfunktsioonid ,
ja
on (*)-arvutatavad.
Lemma 2. ([1], 26) Olgu funktsioonid
ja
(*)-arvutatavad ning
siis on ka funktsioon
(*)-arvutatav.
Lemma 3. ([1], 28) Olgu funktsioonid
ja
(*)-arvutatavad ning
siis on ka funktsioon
(*)-arvutatav.
Lemma 4. ([1], 29) Olgu funktsioon
(*)-arvutatav ning
siis ka funktsioon
(*)-arvutatav.
Kõikide lemmade ja esitatud teoreemi tõestused on vormistatud viidatud materjalis . Nii palju võib öelda, et iga lemma tõestamiseks on vaja konstrueerida vastav Turingi masin, mis rahuldaks (*)-arvutatavuse kahte tingimust.
Siinkohal esitame ainult meid huvitava tõestuse, milleks on Lemma 4 tõestus.
Lemma 4 tõestus. ([1], 29-30). Kõigepealt konstrueerime masina, mis lisab lindile paremale vahetulemusi ja arvutab järjestikku
kuni mingil
väärtusel saadakse
väärtuseks . Lindile kirjutatakse :
kus
Turingi masin, mis töötab seisust
alustamise korral järgmiselt:
1) kirjutab korteeži taha arvu ,
2) kopeerib sinna järele arvud ,
3) asendab esimesena kirjutatud nulli tühikuga ja viib pea tagumise
nulli juurde.
Turingi masin, mis arvutab funktsiooni
väärtust, milleks on .
Turingi masin, mis arvutab funktsiooni
väärtusi.
Turingi masin, mis arvutab valikufunktsiooni
väärtust, tuues korteežist paremale välja paremalt lugedes -nda komponendi.
Turingi masin, mis on masina
-kordne kompositsioon iseendaga ehk see masin annab tulemuseks rea .
Turingi masin, mis on masinate
ja
kompositsioon.
on masin, mis lindil oleva viimase arvu nulli kohalt alustades lisab arvu lõppu kriipsu ja viib pea nulli kohale tagasi. Kompositsioonina
tekitavad nad lindile funktsiooni
ette arvu, mis on funktsiooni
argumentide -l kohal.
Kompositsiooni, hargnemise ja suunamise abil saame konstrueerida masina, mis eelnevaid arvutusi teeks selliselt nagu oli näidatud. Tähistame seda masinat sümboliga . Saame
kus
on Turingi masin, mis lindil nulli kohal alustades lõpetab oma töö lindil midagi muutmata seisundis , kui nulli taga on tühik, ja seisundis , kui nulli taga on kriips . Nool tähistab juhtimise üleandmist masina
esimesele seisundile.
Valides
saame masina, mis arvutab funktsiooni . Turingi masin
nihutab pea all oleva nulliga algava arvu vasakule esimese mittetühja sümboli taha ja paneb pea selle arvu nullile ning masin
kustutab lindilt kõik peast vasakul asuvad nullid ja kriipsud kuni esimese tühikuni ja toob pea tagasi.
Tingimus 1*) on täidetud, sest kõik kompositsioonis esinevad Turingi masinad on konstrueeritud (*)-arvutatavuse tingimusi silmas pidades ehk vastava funktsiooni väärtuse arvutamisel ei asu masina lugev-kirjutab pea lindil kunagi vasakul pool argumentide esimest vasakpoolset pesa, mida näitab see, mis lindile kirjutatakse, kui antud masina töötavad. Järelikult masina ka
korral on tingimus 1) täidetud.
Tingimuse 2*) kontrolliks vaatleme kahte võimalikku olukorda, kus
pole määratud. Need olukorrad on järgmised:
1)
on iga arvu
korral määratud, kuid erineb nullist,
2) arvutusel jõutakse arvu
sellise väärtuseni, kus
pole määratud.
Olukord 1 on see, mille tõttu mitte kõikjal defineeritud funktsioonid arvutustes tekivad: hakatakse otsima seda, mida tegelikult ei leidu. Olukord 2 on aga see, mille tõttu me ei saa algoritmiliselt leida seda, mida tegelikult tahaksime s.o. tingimust
rahuldavat vähimat arvu.
Tulla tagasi lemma juurde, kui
erineb nullist iga arvu
korral, siis jätkab masin
lõpmatult lindile uute arvude kirjutamist ja arvutus ei lõpe. Kui aga masin
jõuab sellise arvu
väärtuseni, et
pole määratud, siis ei lõpeta masin
nendel argumentidel tööd, sest lemma eelduse põhjal rahuldab masin
tingimust 2*). Näeme, et mõlemas olukorras töötab masin
lõpmatult ja seega on tingimus 2*) täidetud, mida tahtsimegi näidata.
Kokkuvõttes saime , et funktsioon
on (*)-arvutatav.
Seega oleme näidanud, et operaatori
abil (*)-arvutatavatest funktsioonidest saadud funktsioonid on samuti (*)-arvutatavad.

Kokkuvõte

Referaadi eesmärgiks on uurida funktsioonide (*)-arvutatavust, mis on saadud operaatori
abil saadud (*)-arvutatavatest funktsioonidest.
Neid protsesse uurides avastasime, et operaatori
abil saadud (*)-arvutatavad funktsioonid on samuti (*)-arvutatavad. Tõdesime ka seda, et iga osaliselt rekursiivne funktsioon on (*)-arvutatav.
Teoreemid , definitsioonid ja lemmad on kõik raamatust [1].

Kasutatud kirjandus

[1] – Prank , Rein (2004). Matemaatiline loogika ja algoritmteooria. Tartu: Tartu Ülikooli Kirjastus.