• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

On the equivalence of Markov Algorithms and Turing Machines and some consequent results

Papathanassiou, Eleftherios January 1979 (has links)
Turing Machines and Markov Algorithms are, and were designed to be, the most powerful devices possible in the field of abstract automata: by their means any and every computable function can be computed. Because of their equal, indeed maximal, strength, it was naturally assumed that these devices should be equivalent. Nonetheless a formal, exact proof of this universally presumed equivalence was lacking. The present dissertation rectifies that omission by developing the desired complete, rigorous proof of the equivalence between Turing Machines and Markov Algorithms. The demonstration is being conducted in a constructionist way: for any given Markov Algorithm it is shown that a Turing Machine can be constructed capable of performing exactly what the Algorithm can do and nothing more, and vice versa. The proof consists in the theoretical construction, given an arbitrary Markov Algorithm, of a Turing Machine behaving in exactly the same way as the Algorithm for all possible inputs; and conversely. Furthermore, the proof is given concrete shape by designing a computer program which can actually carry out the said theoretical constructions. The equivalence between TM and MA as proven in the first part of our thesis, is being used in the second part for establishing some important consequent results: Thus the equivalence of Deterministic and Nondeterministic MA, of TM and Type 0 Grammars, and of Labelled and Unlabelled MA is concisely shown, and the use of TM as recognizers for type 1 and 3 grammars exclusively is exhibited. It is interesting that, by utilizing the equivalence of TM and MA, it was made possible that the proofs of these latter results be based on primitive principles.

Page generated in 0.0731 seconds