Turing Machines, Cayley Graphs, and Inescapable Groups.
Aubrey da Cunha · Deep Blue (University of Michigan) · 2012
We present a generalization of standard Turing machines based on allowing unusual tapes. We present a set of reasonable constraints on tape geometry and conclude that the proper degree of generality 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. We also get a comparable result for the polynomial time degrees and relate this to the difficulty of proving lower bounds in computational complexity. The definitions and constructions involved give rise to a number of questions about computable paths inside Cayley graphs of finitely generated groups, and several of these questions are answered.