Graph Grammars on Galois Machines
Joshua Herman, Keith David Pedersen · arXiv (Cornell University) · 2008
The Turing machine has been the paradigm in computation since it was proposed in the 1930s by Alan Turing. However the power of Turing’s machine is limited by its foundation in binary numbers, as Turing himself pointed out when he proposed the ”Oracle,” a vastly superior computer that would compute the answer of operations in one single step, not multiple steps. In an attempt to realize at least some of the functionality of Turing’s ”Oracle,” we present a new automaton- Abstract Graph Galois Machines (AGGM). AGGMs operate on the Euclidean Galois field [10] and their architecture is an abstraction of the graphs of graph theory. The computing power of AGGMs arises from automorphisms on Euclidean Space [1]. The advantage to this approach is a method of implementation of the Blum Shub Smale machine (i.e., the ”Oracle”). [6] [5] We have attempted to prove that AGGMs are expressible as automata [?], with all of the expressive power of a Turing machine and more.