World memory

You know that old trick for finding your way out of a maze? You keep your left hand touching the wall the whole time, leading you to follow a series of left turns that will, inevitably, bring you to the exit. It's a fascinatingly simple algorithm, and an interesting way to understand it is as a kind of depth-first search.

A depth-first search is one way of exploring a space where, each time you have a choice, you pick the first option. Repeat until you get stuck, at which point you go back to your most recent choice and pick the second option. If you're out of options, you go back further. It's called depth-first because you go down each path as far as you can before exploring any other options.

To use this algorithm, though, you need to keep track of where you've been. After all, when I say "go back to your most recent choice", what was it? And when I say "first option", "second option", etc, how do you know which one you're up to? You need to keep some kind of list so you can know where to go next. But, for some reason, the left-hand-following-the-wall solution doesn't use one – how can that be?

Well, imagine a Y shaped passage, where you enter from one side and the other two are dead ends. If you keep your left hand on the wall, you'll take the left fork first, then when you hit the dead end, you follow the wall around to the right fork, which leads you around the dead end back out the way you came.

Play that again in slow motion: the wall leads you back to your most recent choice when you hit a dead end, and the wall connects each option to the one after it. The reason you don't need to keep a list of decisions is because the wall and the list are equivalent. Or, to put it another way, somebody already stored that list in the form of a wall.

The memory requirement of the algorithm hasn't been overcome, we're just using the physical world as memory. Not in the symbolic way that marks on paper are physical, but profoundly, concretely. The walls create a maze, but in doing so they also store a path that explores the maze.