Izračunljivi brojevi

master's thesis

• Author: Maja Budimir
• Mentor: Zvonko Iljazović (mentor)
• Committee member: Zvonko Iljazović (predsjednik povjerenstva)
• Committee member: Maja Resman (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Committee member: Dragutin Svrtan (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: RAM-stroj; izračunljiva funkcija; izračunljivi brojevi; konačnost skupova; prebrojivost skupova; neizračunljivi realni brojevi
• Keywords (english): random-access machine; computable function; computable numbers; finiteness of sets; countability of sets; incomputable real numbers
• Language: croatian
• URN:NBN: urn:nbn:hr:217:589355
• Study programme: Title: Mathematics Education; specializations in: Mathematics Education; Course: Mathematics Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike (magistar/magistra edukacije matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2017-12-20 11:44:28