**Distance functions on computable graphs**

Consider a connected infinite graph. A natural question one might ask about a given pair of vertices on the graph is, “What’s the shortest path between these two nodes?” We study the algorithmic complexity of this question for n is computationally as hard as it could possibly be.

*computable*graphs (a graph is computable if its edge relation is algorithmically decidable). Specifically, we define the*distance function*for a graph (it is what you think it is) and discover some interesting properties. In fact, we’ll see algorithmic properties of a whole family of functions that, like the distance function, have a*computable decreasing approximation*(that is also probably what you think it is). In the end, we’ll be able to encode complex information into the structure of a graph so that the corresponding distance functioThis work is joint with Wesley Calvert and Russell Miller.