Dimension 1 sequences are close to randoms

Logic Seminar

Meeting Details

For more information about this meeting, contact Jan Reimann.

Speaker: Linda Westrick, University of Connecticut

Abstract: We show that an infinite binary sequence has effective dimension 1 if and only if it differs from a Martin-Loef random on a set of density zero. More generally, a sequence has effective dimension at least s if and only if it differs from a weakly s-random on a set of density zero. We also characterize the density of changes required to increase the effective dimension of a given sequence by a specified amount. Joint work with Greenberg, Miller and Shen.


Room Reservation Information

Room Number: 315 McAllister

Date: 10/31/2017

Time: 2:30pm - 4:00pm