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).
Randomness and relativization
09.03.2006 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25