Complejidad computacional. Cintas de Máquinas de Turing que son Grafos de Cayley Infinitos.

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 defined his a-machines, which would later be called Turing machines [20], 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 defining the term “computable”, and as adding tapes and dimensions defined 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 different tape geometries. This led to a number of results about relative efficiency 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 finite 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 satisfied by a reasonable tape. It turns out that the criteria we outline are necessary and sufficient conditions for the graph to be the Cayley graph of a finitely generated, infinite 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 definition 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, efficient. This allows us to draw connections between resource bounded computations over Cayley graphs and well-known time and space classes. A side effect 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 find in arbitrary Cayley graphs. In particular, whether we can always find an infinite, 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 finite order, yet be infinite. Such a group is called a Burnside group and the existence of Burnside groups was an open problem for some time.


Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: