This question is equivalent to asking if a finite-state-automaton can decide or accept a particular language, or if a push-down automaton could. I believe the only way to deduce the self-intersection or self-avoiding nature of a walk based on relative moves of {turn left, move forward, turn right} is to turn them into a sequence of absolute moves and simulate them on the square lattice, keeping track of state along the way.

**Summary:**

Convert the sequence of relative moves into a sequence of absolute moves. This step is not absolutely necessary but helps to make the next step easier to understand.

for any sequence of $n$ absolute moves $m_1 m_2 ...m_n,$ with $m_i \in$ {N,S,E,W}, it self-intersects if it contains a subsequence

$m_a m_{a+1}...m_b$, such that $1 \le a\lt b \le n$

such that the subsequence contains exactly the same number of $N$ as it does of $S$ and exactly the same number of $E$ as $W$.

This is equivalent to and can be restated as $N^cE^dS^cW^d$, or as saying $\Delta$(Longitude)$=0$ and $\Delta$(Latitude)$=0$.

Deciding a regular language $x^n y^n$ (or in this case $N^c S^c E^d W^d$ ) can not be decided by a FSA (finite state automaton) but can be decided by a push-down automaton, which keeps track of state in the push-down stack. My reference for computability or acceptability by a Finite State Automaton is (for me, in this case) Papadimitriou and Lewis *Elements of the Theory of Computation*, which I remember from my undergraduate course in computation theory. I don't remember the original source described in the book, though. In this case, the push-down stack is keeping track of the state of either the number of N,S,E,W, via the direction traveled or the state of which squares have been visited thus far. Either way is equivalent, and effectively requires simulating the walk.

I believe the only way to deduce the self-intersection or self-avoiding nature of a walk based on relative moves of {turn left, move forward, turn right} is to turn them into a sequence of absolute moves and simulate them on the square lattice. The reason for this is that the self-intersection may occur in two squares as the sequence (move forward), (turn left | turn right)${}^3$, (move forward). It may also occur $n$ steps later, with $n>1$, as in ( (move forward)${}^{10}$, (turn right) )${}^4$ which self intersects as a square of width $10$ after eighty relative moves $=$ forty absolute moves.

If you were to look at a series of relative moves or turtle-graphics-moves as a series of symbols, and attempt to apply some symbolic dynamics rules such as replace a (forward)(turnaround)(forward) $\to$ (INTERSECTIONFOUND), or (turn right)${}^3 \to$ (turn around), etc., then it would not be possible to create enough rules to keep track of state of each possible lattice point in the square lattice. You have to keep track of the state of the lattice points as having been "visited" or "not visited" and simulate the entirety of the walk or at least enough of the walk until an intersection first occurs in order to determine that the walk is self-intersecting.

You must simulate the entire length of the walk to determine that it is not self-intersecting.

This is similar to the result that certain languages are not acceptable or decideable by a finite-state-machine, but are decideable or acceptable by a **push-down-stack** turing machine: the canonical example is designing a finite-state-machine which decides the language $a^nb^n$ or checks for matching right-parentheses for every left-parenthesis. This type of matching exercise, where $n$ copies of the symbol $a$ are followed by exactly $n$ copies of the symbol $b$ are not recognizable by a finite state automaton, but can be recognized by a push-down automaton (also known as a stack-based finite-state-machine).

If instead, I think you are trying to ask if there are rules that can be applied locally, where by locally I mean by observing only the local neighborhood (which can be the Von Neumann neighborhood [N,S,E,W] or Moore neighborhood [NW,N,NE, W, E, SW, S, SE] in 2-d, or all nodes connected by edges to the current edge for cellular automata on a graph) and capture the behaviour of a self-avoiding walk.

Purely local rules are not enough to capture the global behaviour necessary to allow for the creation of a self-avoiding walk **unless** the cells to be walked on are also allowed to store "state" for their location. If a cell can also have associated with it a "state" corresponding to "having been walked on" as $1$ and "never having been walked on" as $0$, then it is possible to define a self-avoiding walk in such a way.

The rules for such a walk would be:

Have the walker change the state of the cell it is currently in to $1$

Have the walker move to a neighboring cell according to your random walk rules and probabilities **only if** that neighboring cell has a state corresponding to "never having been walked on" $=0$

iterate until it is impossible for the walker to move in any direction (corresponding to all of the neighboring cells of the current position already having been walked on)

Thus to model or simulate something which captures global properties in this case, it is important to allow the model to hold and represent the global property of "the path walked thus far". It's also akin to and contrary to the ant-walking algorithms with the ants leaving a pheremone trail which can increase the likelihood of further walkers following a particular path. It's also similar to creating a path for a painter to walk without being "painted into a corner".

4more comments