"arvutatavust" - 1 õppematerjal

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

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.