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