Izračunljivi brojevi

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.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