Distance functions on computable graphs

Jennifer Chubb
Associate Professor University of San Francisco

Stevenson Hall 1300
12:00 PM - 12:50 PM

An infinite graph---one made of nodes and edges---is computable if there is an algorithm that can decide whether or not a given pair of nodes is connected by an edge.  So, for example, the internet is a computable graph which is, for all intents and purposes, infinite.  Now, given two nodes on a connected, computable graph, a natural question to ask is, What is the length of the shortest path between them, i.e., the distance between the nodes?  Of course, for a connected graph we can always find such a path and determine its length, but the question of finding a shortest path is harder, and is not in general something we can compute for infinite computable graphs.

In this talk, we will see what it means for something to be non-computable via a classic example called the halting problem.   Next we will see that it's possible to encode non-computable information into even very simple, computable mathematical objects.  Finally, we will see how non-computable information can be encoded into the distance function, the function which outputs the shortest distance between two nodes of a given graph.  So, the answer to What is the shortest path between two nodes?  Well, we may never know for sure.

This work is joint with Wesley Calvert and Russell Miller.