Series: Penn State Logic Seminar

Date: Tuesday, April 17, 2001

Time: 2:30 - 3:20 PM

Place: 316 Willard Building

Speaker: Stephen Binns, Mathematics, Penn State

Title: Paths Through Recursive Trees, part 2

Abstract: 

A recursive tree is a computable set of binary strings with a simple
branching structure.  Even though a tree itself may be computable,
computing an infinite path through a tree can sometimes be impossible.
How much information do we need to find a path?  Can knowing a path
through one tree help us find a path through another?  Is there a
"universal" tree that will give us a path through any other?  This
talk will answer these questions and go deeper into the structure of
the collection of all trees.  Very little about this structure is
known and there are far more questions than answers.  The talk is the
essential parts of a recent paper of Stephen Simpson and Stephen
Binns.