Can two deterministic turing-machines avoid each other in a sidewalk? Imagine a turn-based game where two robots are placed on opposite sides of a 16x16 board, facing each-other. Each robot, at each turn, can perform one of 2 moves: move (moves forward), turn (turns 90 degree; clockwise for the first robot, anti-clockwise for the second). They can also send messages to each-other, and behave according to arbitrary deterministic computations.

|_|_|_|_|v|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|^|_|_|_|_|


For simplicity, assume the behavior of the robots is determined by a Python function such as:

# just an example, not used
state = {}

# always go forwards
def brain(otherPos, myPos, message):
    return ("move", "hello")


This behavior is, of course, stupid, as it always goes forward and broadcasts the same message, ignoring the position of the other robot and the message sent by it. On this case, the robots would just go forward, until they colide and stop moving forever. But any logic could be implemented and the robots could collaborate in arbitrary ways. An improvement would be:

# just an example, not used
state = {turn: 0}

# always go forwards
def brain(otherPos, myPos, message):
    if state.turn === 0:
        return ("turn", "I'm turning")
    elif state.turn === 1:
        return ("move", "I'm moving horizontally")
    elif state.turn &lt;= 4:
        return ("turn", "I'm turning again")
    else:
        return ("move", "Now I'm going forward, forever!")


This one would cause both robots to turn 90 degrees, move, then turn 3 times, and then move forward forever. They'd still collide and get stuck on the same column, though, because, as one turns clockwise, the other one turns anti-clockwise.

My question is: is it possible to program a brain function in such a way that, after N turns, each robot ends up on the other side?
You have to teach the robots how to keep track of their identity, either by remembering the initial position, or by signing their messages.
Then they can perform their individual programs. 
Something like this: 

t = "turn"
m = "move"
program1 = [t, m, t, t, t, m, m, m, m, m, m, m]
program2 = [t, t, t, m, t, m, m, m, m, m, m, m]

def brain(otherPos, myPos, message):
    if message == "1":
        return (program1.pop(0), "2")
    else:
        return (program2.pop(0), "1")