Series: Penn State Logic Seminar

Date: Tuesday, January 30, 2001

Time: 2:30 - 3:20 PM

Place: 316 Willard Building

Speaker: Stephen Binns, Mathematics, Penn State

Title: Paths Through Recursive Trees

Abstract: 

A recursive tree is an (infinite) computable set of binary strings
with a simple branching structure.  Even though a tree itself may be
computable, however, 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 paper just written by Stephen Simpson
and Stephen Binns.