# Can two deterministic turing-machines avoid each other in a sidewalk? [closed]

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 <= 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?

• Both turn to there left. Both move forward one time, then both turn to get there initial direction. Then both move forward. No ? – user80502 Dec 1 '17 at 16:35
• @dylan61 the trick is how to turn each robot on their left. The game seems to be formulated so that the robots always move symmetrically. – jmster Dec 2 '17 at 10:55
• How exactly does the game work? Do the robots take turns to move? If so, you can break the symmetry by using the fact that one of the robots moved to be adjacent to the other. How does message broadcasting work? Do the robots know their position? – David Richerby Dec 2 '17 at 12:23
• For now, I'm voting to close as unclear since the rules aren't specified. – David Richerby Dec 2 '17 at 13:36
• @DavidRicherby the game works in turns, each turn a robot picks a move, robot A moves, then robot B moves, and messages broadcasted are only received on the next turn (the robots can't know which one moved first). – MaiaVictor Dec 8 '17 at 11:38

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")

• Indeed, you could just do if id==1 {/* run program 1 /*} else { /* run program 2 */}. None of these ideas is forbidden by the question. – David Richerby Dec 2 '17 at 13:35
• @DavidRicherby jmster's program would cause both robots to execute the second branch on the first turn, and receive message "1" on the second turn. Sorry for the delay in answering those questions, next time I ask something like that I'll provide an interpreter for absolute clarity. – MaiaVictor Dec 8 '17 at 11:40
• @MaiaVictor I see, it 's a very special "turn-based game" you have. In that case please specify what do myPos and otherPos mean. If at least one of them contain the absolute coordinates, the robots can use that to identify themselves on the first move. If each robot believes it stands on row 1, then sorry. – jmster Dec 8 '17 at 22:16

The only way I can think of is to make them choose a random direction (left or right) and broadcast it, if they broadcast one direction and receive the other then they repeat and they do this until they both go once in the same direction. When they know this they move up the board.

• Deterministic Turing machines have no access to randomness. – David Richerby Dec 2 '17 at 12:24
• Ok, sorry, guess I didn't fully understand the question – 13ros27 Dec 2 '17 at 13:37