He encontrado por casualidad esta reciente tesis (2012) sobre el tema del título.
Título. Turing Machines, Cayley Graphs and inescapable groups.
When Alan Turing originally deﬁned his a-machines, which would later be called Turing machines , he envisioned a machine whose memory was laid out along a one-dimensional tape, inspired by the ticker tapes of the day. This seemed somewhat arbitrary and perhaps unduly restrictive, and so, very quickly, machines with multiple and multi-dimensional tapes were proposed. The focus at the time was deﬁning the term “computable”, and as adding tapes and dimensions deﬁned the same class of functions as Turing’s original, simpler model, studying alternate tape geometries fell out of favor for some time.
The complexity theory community then reignited interest in alternative tape geometries by considering not the class of functions computable by Turing machines, but time and space complexity of functions on diﬀerent tape geometries. This led to a number of results about relative eﬃciency of machines with one/many tapes and one/two/high-dimensional tapes.
Many of the proofs and algorithms used in the study of multidimensional Turing machines make their way into or are inspired by the world of mesh-connected systems. Mesh-connected systems are arrays of identical, relatively dumb processors (typically with memory logarithmic in the input size) that communicate with their neighbors to perform a computation. Time use on a Turing machine with a d-dimensional tape is intimately tied to the power use of a d-dimensional mesh of processors with ﬁnite memory, so there is some natural crossover. Mesh-connected systems constitute an area of very active research now, but since it remains very closely tied to the physical
implementation, research is generally restricted to two- and three-dimensional grids.
It is natural, then, to ask how far we can push the notion of a tape. In this thesis, we go beyond the world of rectangular grids and consider tapes at their most general. The purpose of this is two-fold.
—First, to give the complexity theorists a general framework in which to work, subsuming all current tape-based Turing models.
–Second, to provide some evidence that alternative tape geometries are interesting from a recursion-theoretic perspective.
Our tapes are static objects and our machines may merely write symbols on the cells of the tape. Any tape of this type can be modeled as a digraph with nodes corresponding to tape cells and edges corresponding to allowable transitions. Hence, we start by introducing a number of graph-theoretic conditions that ought to be satisﬁed by a reasonable tape. It turns out that the criteria we outline are necessary and suﬃcient conditions for the graph to be the Cayley graph of a ﬁnitely generated, inﬁnite group.
We then turn to the question of whether allowing arbitrary Cayley graphs as
tapes is just another equivalent machine model for the class of computable functions. Interestingly, this will depend on the structure of the group from which the Cayley graph is generated.
–For groups with solvable word problem, this does indeed lead to machines that compute the class of computable functions,
–however for groups with unsolvable word problems, these machines are strictly more powerful than standard Turing machines.
In fact, they can be as powerful as any oracle machine and we end
up with an alternative deﬁnition of the Turing degrees that is machine based and doesn’t rely on oracles. We observe at this point that the simulations used to show the power of machines over arbitrary graphs are, in fact, eﬃcient. This allows us to draw connections between resource bounded computations over Cayley graphs and well-known time and space classes. A side eﬀect of this is the observation that attempts at using very low-level combinatorial arguments to defeat relativization barriers will have to make essential use of the structure of the underlying tape.
The constructions and proofs of these results begin to raise questions about what kind of computable objects we can hope to ﬁnd in arbitrary Cayley graphs. In particular, whether we can always ﬁnd an inﬁnite, computable, non-self-intersecting path. We call such a path an escape and we construct a group without any escapes. This construction is non-trivial as any group without an escape must consist entirely of elements of ﬁnite order, yet be inﬁnite. Such a group is called a Burnside group and the existence of Burnside groups was an open problem for some time.