Remark on the Computational Power
of a Turing Machine Variant
by Lionel E. Deimel
While I was still an undergraduate at the University of Chicago, I attended a
von Neumannís theory of self-reproducing automata. Automata are abstract
computing devices. Von Neumannís work in automata theory was fascinating but was
only one of his many contributions to what would become computer science. His
automata were devilishly clever and their construction had an air of
puzzle-solving about them. I didnít know it at the time, but I would go on to do
my doctoral thesis in automata theory, inspired in part my von Neumann.
ďRemark on the Computational Power of a Turing Machine VariantĒ (citation) was my first
published paper, which was written while I was a graduate student. Although the
paper involves a type of automaton, the work was only tangentially related to my
dissertation topic, which involved a different class of automata.
A Turing machine, named for mathematician
is an abstract machine, i.e., an automaton, that is capable of executing any
algorithm that can be performed by a deterministic computer. A Turing machine is
intended to capture the minimum mechanisms needed for general-purpose
computation. In fact, automata slightly less capable can still do what Turing
machines can do.
My 1974 paper establishes that what I call a restricted D-machine, a
Turing machine variant, is, in a sense, less capable than a D-machine, which is
as capable as a Turing machine. The paper makes this argument formally.
I donít know that my paper advanced the theory of computing, but writing it
was good practice for my dissertation, which was much more complex.
|Remark on the Computational Power of a Turing
Machine Variant (PDF)
ó LED, 4/19/2023