# 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.

### Exercises

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

• C,K are incomputable using the recursion theorem

• C,K are incomputable without using the recursion theorem

• \Omega:=\sum_{\sigma} 2^{-K(\sigma)} is random, using recursion theorem

• \Omega:=\sum_{\sigma} 2^{-K(\sigma)} is random without recursion theorem

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

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

• B_c := \{\sigma : K(\sigma)< |\sigma|+K(|\sigma|)-c\} is not c.e.

• G_c := \{\sigma : K(\sigma)< K(|\sigma|)+c \} is not c.e.

Using computability theory:

• prove Godel’s first incompletness theorem using the recursion theorem

• prove Godel’s first incompletness theorem without the recursion theorem

### Short Clips 