9 December 2014, Logic Tea, Merlin Carl

Abstract

Algorithmic randomness provides an attractive formalization for the intuitive notion of a "lawless", "arbitrary" sequence. We consider algorithmic randomness for machine models of infinitary computations. We show that a theorem of Sacks, according to which a real x is computable from a randomly chosen real with positive probability iff it is recursive holds for many of these models, but is independent of ZFC for ordinal Turing machines. Roughly, this means that the rather plausible intuition that random sequences cannot be informative is provable for very restrictive notions of "random sequence" and at some point motivates statements that go beyond that which is decidable in the generally accepted axioms of mathematics.

For more information, please visit the website http://www.illc.uva.nl/logic_tea/ or contact Thomas Brochhagen (t.s.brochhagen at uva.nl), Johannes Marti (johannes.marti at gmail.com), Masa Mocnik (masa.mocnik at gmail.com) or Julian Schloder (julian.schloeder at gmail.com).