Computing Reviews

One head machines from a symbolic approach
Gajardo A., Mazoyer J. Theoretical Computer Science370(1-3):34-47,2007.Type:Article
Date Reviewed: 06/01/07

This paper proposes a new computing machine model, a modified Turing machine, and studies properties of the proposed model. The major modification the authors propose is to allow for a tape in the form of a Cayley graph. In other words, their new model would build a dynamic symbol system using mathematical structures such as Turing machines, Abelian groups, pushdown automata, and Cayley graphs.

The paper consists of seven sections. Section 1 provides a brief introduction. The second section supplies background information and defines terms such as word, language, topological dynamical system, pushdown automaton, and subshift. Section 3 presents the basics of Cayley graphs. The section includes an example of a Cayley graph for two different groups. The fourth section begins by defining subshift and related terms with respect to a Turing machine; relevant properties are presented in the form of two remarks. Sections 5 and 6 present the major part of the work. They contain proofs of several major propositions describing properties of the proposed model. Section 7 concludes the paper.

The paper is highly theoretical with some examples for explanation. It is assumed that readers will have a strong background in theoretical computer science and discrete mathematics. The authors attempt to open new possibilities of research. However, they avoid showing any other applications of the work.

Reviewer:  Maulik A. Dave Review #: CR134348 (0805-0491)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy