20.500.12556/RUL-124754 Univerzalni računski modeli Turing complete models 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. 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. univerzalni računski modeli Turingovi stroji sistemi oznak celični avtomati Turing complete models Turing machines tag systems cellular automata true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2021-02-15 08:28:51 2021-02-15 08:28:55 2023-11-27 12:02:28 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 26424 51606787 Percinic_Martin_-_Univerzalni_racunski_modeli.pdf Percinic_Martin_-_Univerzalni_racunski_modeli.pdf 1 F7A2F7E4838BD51999E37637E5EDCEF6 f1e85c043f7fad034df56997bf165992fb741e1d9021b4a630311f86475e3166 9d85c8cd-a1bb-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=140358 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0