Logic Seminar-Computable directed graphs with non-computable properties
Wed, 12 April, 2017
9:30pm
Wednesday, April 12, 2017
5:30–6:30p.m.
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.