|
|
Universal Turing machine
Bahýľ, Viktor ; Krajíček, Jan (advisor) ; Holub, Štěpán (referee)
Title: Universal Turing machine Author: Viktor Bahýľ Department: Department of Algebra Supervisor: RNDr. Jan Krajíček, DrSc., Department of Algebra Abstract: This thesis is focused on the processes of solving computational problems. The Turing machine is an example of a model which we can use to solve these problems and these machines are the main objective of this Bachelor thesis. The generality of the model is important; it allows us to simulate any conceivable algorithm. In the theory of Turing machines, the generality is demonstrated by the construction of a universal Turing machine. This is the task of this Thesis: to define a universal Turing machine and to prove its universality. Key definitions, linked with the Turing machines, are recalled at the beginning of the Thesis. The simulation and representation of Turing machines will prove to be the key concepts. We make an extra effort to explain these fundamental notions. The thesis has its own form of representation and defined Turing machine with detailed descriptions for them, together with complete proof of the universality of the mentioned Turing machine. Keywords: Turing, machine, universality, representation
|
guest ::
