Monthly Suggestions - 22nd August 2023

Self-reference and games in complexity

Read (Downey/Hirschfeldt book, Theorem 16.3.2)

Kummer’s theorem that the non-random strings form a truth-table complete set.

Nice demo of nonuniformity and self-reference via the recursion theorem.


Let C, K be the plain and prefix-free Kolmogorov complexities. Show that

Not as easy as it looks (can you do it?)

For sufficiently large c show that (solution can be found in papers):

Using computability theory:

Advanced self-referencial proofs with complexity

Short Clips

Interviews and talks