Univerzalni računski modeli

Perčinić, Martin (author), Robič, Borut (mentor)

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.

• Language: Slovenian
• Keywords: univerzalni računski modeli, Turingovi stroji, sistemi oznak, celični avtomati
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science ; FMF - Faculty of Mathematics and Physics
• Year: 2021
• PID: 20.500.12556/RUL-124754
• COBISS.SI-ID: 51606787
• Publication date in RUL: 15.02.2021

Secondary language

• Language: English
• Title: Turing complete models

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.

• Keywords: Turing complete models, Turing machines, tag systems, cellular automata