Thesis Summary:

An automaton with a spindle moves in a discrete space at discrete time and is composed of a finite set of internal states, a head capable of reading the information stored in the position in which it is located and writing in it, and a function of transition; Which in each iteration, depending on the internal state in which the PLC is located and the information of the box visited, will dictate the new internal state, the information that will leave in the box and the direction in which the head will move in said iteration. The machines with stones are similar to an automaton of a head only that the only way they have to mark their environment consists in the use of a certain number of stones. These stones can be deposited in the grid and collected from this, and are also enumerated or colored, that is, they are stones differentiable from each other. These machines were introduced by Blum and Hewitt with the motivation of the recognition of guras. The subsequent work of Delorme and Mazoyer shows that 3 stones give him as much power as a Turing machine, but with 2 stones his limited behavior. In this report we approach a concept introduced by Gajardo and Mazoyer called t-shift, which consists in following the path of a machine by recording the sequence of internal states and symbols read at each iteration. The t-shift associated with some machine with a head defines a language, and the complexity of this is closely related to the complexity of the dynamics exhibited by the machine with head. By explicit construction, we show that the t-shift of a machine with 2 stones and 0 symbols can be recognized by a deterministic automaton with 2 stacks, in addition we prove that a deterministic automaton with 1 stack is not able to recognize the t-shift Associated with certain machines with 2 stones, proving with this that the t-shift of a machine of 2 stones need to of two piles to be recognized. In addition, in Chapter 1 we study 2 particular rules within a special class of head machines that generalize the Langton Ant called bees, demonstrating that one of these rules is isomorphic in reverse of the other, and that the complexity of t -shift associated with, exceeds that of regular language.