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
lecture on
John
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
Alan Turing,
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
|
