Low for Randomness

This is a seminar I might organise next semester.

The goal is to go through the line of research around the computational power of randomness. A random real (in $2^\omega$) Algorithmic randomness is the randomness notion from the view of a computer.

Low for randomness (Computability and Randomness - book by André Nies)

• Introduction
• Equivalence of low for K, low for ML-random, base for ML-random
• Cost functions
• K-trivial to low for K
• Low for dimension
• Injury-free proof (for FM, Post's problem)

Random but low computational information

• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension(Joe Miller)
• Diagonally non-recursive functions and effective Hausdorff dimension(Joe Miller, Noam Greenberg)

A list of open questions guilding the seminar

• Is it true that for all Scott set $S$, $Th_{\Sigma_2}([S]_{\equiv_T},\leq_T)=Th_{\Sigma_2}([2^\omega]_{\equiv_T},\leq_T)$?