Kurt Gödel Research Center

2006 seminar talk: Randomness and relativization

Talk held by Sebastiaan Terwijn (TU Wien) at the KGRC seminar on 2006-03-09.

Abstract

This will be an informal low-brow talk on some recent developments in recursion theory on random and generic sets. We will discuss several relations between randomness of finite strings and the theory of finite strings (Kolmogorov complexity). As it turns out, the notion of relativized computation plays a crucial role here. This is joint work with Andre Nies (Auckland) and Frank Stephan (Sydney).