Turing Machines, Cayley Graphs, and Inescapable Groups.

[摘要] 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.

[发布机构] University of Michigan

[效力级别] Cayley Graph

[关键词] Turing Machine;Cayley Graph;Turing Degree;Computability;Mathematics;Science;Mathematics