Turing Machines on Cayley Graphs

摘要

We present a generalization of standard Turing machines based on allowing unusual tapes. We present a set of reasonable con straints on tape geometry and conclude that the proper degree of gener ality is Cayley graphs. Surprisingly, this generalization does not lead to yet another equivalent formulation of the notion of computable function. Rather, it gives an alternative definition of the recursively enumerable Turing degrees that does not rely on oracles.