Univerzalni računski modeli

diplomsko delo

Martin Perčinić (Author), Borut Robič (Mentor)

Abstract

V diplomskem delu obravnavamo univerzalne računske modele oziroma računske modele, ki imajo enako računsko moč kot Turingovi stroji. V prvem delu diplomskega dela opišemo zgradbo in delovanje Turingovega in univerzalnega Turingovega stroja. V nadaljevanju obravnavamo sisteme oznak in celične avtomate, ki so univerzalni računski modeli, namenjeni računanju. Dokažemo njihovo univerzalnost in opišemo njihovo pomembnost pri dokazovanju univerzalnosti drugih sistemov. V zadnjem delu obravnavamo programske jezike in pogoje za njihovo univerzalnost. Obravnavamo tudi univerzalnost strojev, ki niso namenjeni računanju, vendar še vedno lahko z njimi računamo. Pri tem obravnavamo aplikaciji Microsoft Excel in Microsoft PowerPoint ter igro Magic: The Gathering.

Keywords

univerzalni računski modeli;Turingovi stroji;sistemi oznak;celični avtomati;računalništvo;računalništvo in informatika;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2021
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[M. Perčinić]
UDC:	004:51(043.2)
COBISS:	51606787
Views:	595
Downloads:	79
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Turing complete models
Secondary abstract:	In this thesis we discuss Turing complete models. These are models of computation, which have the same computational power as Turing machines. In the first part of the thesis we review the structure and operation of Turing machines and universal Turing machines. In the next part, we introduce tag systems and cellular automata, which are Turing complete models intended for computational purposes. We explain the proof of their completeness and also show their importance in proving the completeness of other models. In the last part we discuss various programming languages and the conditions for their completeness. We also take a look at the completeness of models that are not intended for computation, but can still be used for computing, namely Microsoft Excel, Microsoft PowerPoint and Magic: The Gathering.
Secondary keywords:	Turing complete models;Turing machines;tag systems;cellular automata;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	50 str.
ID:	12559523