Project FONDECYT 1090568
Fundamental Areas
March 2009 - February 2012
Anahi Gajardo [P]:
One Head Machines and their Associated Symbolic Systems
Summary:
PROPOSAL ABSTRACT: Must be clear and informative. Describe the main issues you plan to address, including goals, methodology and expected outcomes. A good summary facilitates an adequate description and understanding of what you intend to achieve. If selected, this abstract may be published in CONICYT’s web page. The maximum length for this section is 1 page. (Arial or Verdana, font size 10). We call “One Head Machine” an automaton that lives in a discrete space. It can walk, read and write symbols, and its behavior is governed, at discrete time, by a deterministic and finitely described rule. Examples of this kind of dynamical systems are the Langton’s Ant, the Pebble Automata, the one head Turing Machines, and the Lorentz Lattice Gas. Such a system can represent a particle that collides with obstacles; a living being that interacts with its environment; an automaton that performs a task, etc. K°urka proposes two different formalizations of one head machines that he called TMT and TMH. We proposed to look at a particular symbolic system associated to TMT which we called t-shift. As we shown in previous projects, the t-shift is sensitive to many of the machine properties, and a parallel can be done between some properties of one head machines and their associated t-shift. In this project we will consider these three systems and study their different dy- namical properties and their interrelations. We will also consider the problem of decidability of several important properties.