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

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