igusa180

Gregory Igusa

Visiting Assistant Professor

B.A., Brandeis University, 2005
Ph.D., University of California, Berkeley, 2013

 

Email: gigusa@nd.edu

Office: 128 Hayes-Healy Hall

Phone: (574) 631-97131

Fax: (574) 631-6579


For additional information see Gregory Igusa’s Personal Page.

Research Interests

My research is in recursion theory, also known as computability theory. Specifically, most of my work has been focused around generic computations and generic reductions. I also enjoy working with other atypical notions of reducibility, and I am interested in effective and reverse mathematical combinatorics, especially work concerning partial orders.
 
Generic computation derives its name from complexity theory, where a given problem can sometimes be shown to be more complex in the generic case than it is in the worst case. So, to generically compute a real is to provide a computation of that real that halts on most inputs (in the sense of limiting density 1) and that always gives correct answers when it does halt. A generic reduction is a generic computation in which your oracle, similarly, does not always give answers when it is asked questions.
 
The Turing degrees embed into the generic degrees, and this embedding provides an interesting perspective from which to view the generic degrees: A Turing degree is hyperarithmetically computable if and only if it embeds below the generic degree of a set with limiting density 1. Also, there exist a large number of quasi-minimal degrees: degrees which are not upper bounds for any embedded Turing degrees, and which, therefore, do not have any information content, at least in the traditional sense of recursion theory. (Such degrees should be familiar to those who work with enumeration reductions.)
 

Selected Publications

  • Gregory Igusa, Nonexistence of Minimal Pairs for Generic Computability. To appear

    in J. Symbolic Logic, see also http://arxiv.org/abs/1202.2560.

 

Please direct questions and comments to: gigusa@nd.edu