For more information about this meeting, contact Stephen Simpson.
| Title: | Everywhere complex sequences and forbidden patterns |
|---|
| Seminar: | Logic Seminar |
|---|
| Speaker: | Alexander Shen, Laboratoire J.-V.Poncelet, Marseille, France |
|---|
| Abstract: |
|---|
| Is there an infinite sequence of bits that is "everywhere complex": every
substring x has complexity at least 0.99|x|-c (where |x| is the
length of x and c is some constant not depending on x)?
(Note that random sequences do not work since they contain all possible
substrings.)
As L. Levin noted, such a sequence indeed exists and can be constructed
by using a Kolmogorov complexity argument. Later M. Ushakov and
A. Rumyantsev found a combinatorial equivalent of this statement and
its relation to the Lovasz Local Lemma. This lemma can be used to prove a
useful generalization of Levin's statement. |
Room Reservation Information
| Room Number: | MB315 |
|---|
| Date: | 03 / 02 / 2010 |
|---|
| Time: | 02:30pm - 03:45pm |
|---|
