Computer Science

Previous ] Home ] Up ]


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)  

Get Adobe Reader

ó LED, 4/19/2023


Previous Home Up

Send mail to Lionel Deimel with questions or comments about Lionel Deimelís Farrago.
Copyright © 2000-2023 by Lionel Deimel. All rights reserved.