Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

9 December 2014, Logic Tea, Merlin Carl

Speaker: Merlin Carl
Title: Infinite Time Algorithmic Randomness
Date: Tuesday 9 December 2014
Time: 17:00-18:00
Location: Room F1.15, Science Park 107, Amsterdam

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 (), Johannes Marti (), Masa Mocnik () or Julian Schloder ().

Please note that this newsitem has been archived, and may contain outdated information or links.