Can two deterministic turing-machines avoid each other in a sidewalk?
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")