Blog Archives

Topic Archive: trees

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20169:45 amLocklin Hall, Room 232, Springfield College

Karen Lange

Climbing (or finding paths) through trees

Wellesley College

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.