Izračunljivi brojevi

diplomski rad

• Autor: Maja Budimir
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Zvonko Iljazović (predsjednik povjerenstva)
• Član povjerenstva: Maja Resman (član povjerenstva)
• Član povjerenstva: Vjekoslav Kovač (član povjerenstva)
• Član povjerenstva: Dragutin Svrtan (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2017-07-18, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ovaj diplomski rad je podijeljen na tri poglavlja. U prvom poglavlju se, koristeći RAM-stroj definira pojam izračunljive funkcije \(\mathbb{N}^{k} \rightarrow \mathbb{N}\) te se proučavaju neka svojstva tih funkcija. U drugom poglavlju definiramo izračunljive funkcije \(\mathbb{N}^{k} \rightarrow \mathbb{Z}\), \(\mathbb{N}^{k} \rightarrow \mathbb{Q}\) i \(\mathbb{N}^{k} \rightarrow \mathbb{R}\). Proučavamo razna svojstva tih funkcija te proučavamo izračunljive brojeve. U trećem poglavlju se bavimo konačnošću i prebrojivošću skupova, dokazujemo da racionalnih i realnih izračunljivih funkcija ima prebrojivo mnogo te da izračunljivih brojeva ima prebrojivo mnogo. Na kraju pokazujemo da postoje neizračunljivi realni brojevi.

Sažetak (engleski)

This diploma thesis is divided into three chapters. In the first chapter, using the notion of a random-access machine, we define the notion of a computable function \(\mathbb{N}^{k} \rightarrow \mathbb{N}\) and we study some properties of these functions. In the second chapter we define computable functions \(\mathbb{N}^{k} \rightarrow \mathbb{Z}\), \(\mathbb{N}^{k} \rightarrow \mathbb{Q}\) and \(\mathbb{N}^{k} \rightarrow \mathbb{R}\). We examine various properties of these functions and we examine computable numbers. In the third chapter we deal with finiteness and countability of sets, we prove that there are only countably many rational and real computable functions and we prove that the set of all computable numbers is countable. At the end we show that there exist incomputable real numbers.

• Ključne riječi: RAM-stroj; izračunljiva funkcija; izračunljivi brojevi; konačnost skupova; prebrojivost skupova; neizračunljivi realni brojevi
• Ključne riječi (engleski): random-access machine; computable function; computable numbers; finiteness of sets; countability of sets; incomputable real numbers
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:589355
• Studijski program: Naziv: Matematika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike (mag. educ. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2017-12-20 11:44:28