2010/05/14 by Aubrey da Cunha, da Cunha, Aubrey
Computer Science · Mathematics · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #acm:03D25 #acm:20E #acm:68Q05 #cs.FL #math.LO #msc:03D25 #msc:20E #msc:68Q05 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1005.2636
18 pages, one table
arxiv created 2010/05/14 · arxiv updated 2010/05/18
We present a generalization of standard Turing machines based on allowing unusual tapes. We present a set of reasonable constraints on tape geometry and classify all tapes conforming to these constraints. 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. The definitions give rise to a number of questions about computable paths inside Cayley graphs of finitely generated groups, and several of these questions are answered.