Speaker: Jennifer Chubb, George Washington University

Title: Computability and the successor relation in linear orderings

Abstract: A countable set is called computable if there is an algorithm for determining membership, and computably enumerable (c.e.) if there is an algorithm for enumerating its elements. A (countable) mathematical structure is computable if its domain, functions, and relations are all uniformly computable. For example, a linear ordering of the natural numbers is computable if there is an algorithm to check if a < b or not. Even when a linear ordering is computable, it is possible that its successor relation is not.

I will review the fundamentals of computability theory needed to investigate the algorithmic complexity of the successor relation on computable linear orderings in the hierarchy of Turing degrees. We will see that for certain linear orderings, there are isomorphic copies with highly complex successor relations. In fact, given any c.e. set, A, of higher algorithmically complexity than the successor relation of the given ordering, it is possible to construct a computable isomorphic copy, L, of the ordering so that the successor relation in L has the same complexity as the set A [1].

[1] J. Chubb, A. Frolov, and V.S. Harizanov, Degree spectra of successor relation of computable linear orderings. (Submitted.)

Place: Science and Technology Building I, Room 242

Refreshments will be served before the talk at 3:00 p.m. in Room 222.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491