Climbing (or finding paths) through trees
You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We’ll see that every binary tree with infinitely many nodes has an infinite path. But can we actually *compute* a path, given that we can prove one exists? Answering this question requires us to carefully define the verb “to compute.” This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.
This talk is aimed primarily at undergraduates.
Karen Lange studies computable model theory, with a focus on the computational complexity of various algebraic structures, including graphs, free groups, and homogeneous models, and in particular on the complexity of structures associated with real closed fields. She received her doctorate from the University of Chicago in 2008, under the supervision of Robert Soare, and subsequently was awarded a National Science Foundation Postdoctoral Research Fellowship for study at Notre Dame University. Currently she is Assistant Professor of Mathematics at Wellesley College.