Structural properties of one-tape Turing machines.

Abstract

The model of Turing machines has been studied since its birth in 1936. Researchers have continuously proposed variants of such a model. Upon imposing different constraints, the power of each model varies or even remains the same, accordingly. Some well-known result (for example, the equivalence of finite state automata and one-tape linear-time deterministic Turing machines) has proven that the abilities of overwriting the tape content and scanning the tape content more than once cannot gain any advantage under certain restrictions. In this thesis, we study the behaviors and the fundamental properties of variants of one-tape Turing machines, such as deterministic, reversible, nondeterministic, probabilistic, and quantum Turing machines. This gives us a better understanding about the strength and the weakness of each machine type. For example, under the one-tape linear-time restriction, reversible, nondeterministic, co-nondeterministic, and bounded-error probabilistic computations recognize exactly regular languages whereas probabilistic and quantum Turing machines can recognize even non-regular languages.