| 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
