Wednesday, October 7, 2015 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Mohammad Mahmoud, Pure Mathematics, University of Waterloo
"Algorithmic Randomness: Introduction to Kolmogorov Complexity"
After
we
have
established
the
machine
existence
(Kraft-Chaitin
Theorem),
this
time
we
are
going
to
give
the
proofs
for
the
following
"desirable"
facts
about
$K$
which
we
stated
before:
(a)
Incompressible
(in
the
sense
of
$K$)
strings
have
only
short
runs
of
zeros
(i.e.
blocks
only
consisting
of
zeros),
and (b)
Zeros
and
ones
occur
balancedly.
MC
5403