Logic Seminar-Computable directed graphs with non-computable properties

Wednesday, April 12, 2017


Speaker: Hakim Walker, GWU

Place: Rome Hall (801 22nd Street), Room 351

Title: Computable directed graphs with non-computable properties

Abstract: In 2014, Cenzer, Harizanov, and Remmel investigated computable injection structures, two-to-one structures, and (2,0):1 structures, all of which are types of infinite directed graphs derived from computable functions. In this talk, we will define a (2,1):1 structure and discuss various related computability-theoretic properties, including branching, branch isomorphisms, computable categoricity, and relative computability categoricity.