Computability Learning Seminar

Julian Cheng, University of Waterloo

An Introduction to Random Binary Sequences

In this week, our goal is to cover two definitions of what it means for an infinite binary sequence to be random: one definition will come from the perspective of computability and the other from measure theory. We will show that they are equivalent. As an example, we will show that Chaitin's constant (also known as the halting probability) is random. This will cover parts of section 6.1 and 6.2 from Downey and Hirschfeldt.

MC 5403