Exercises

Question 1

Prove that \(f: \set{0,1}^* \to {\mathbb{R}}\) is computable if and only if it is both lower and upper semi-computable.

Question 2

Prove that a function \(f: \set{0,1}^* \to {\mathbb{R}}\) is lower semicomputable if and only if its lower graph

\[G^-(f)=\set{(x,q)\in\set{0,1}^*\times\mathbb{Q}\mid q<f(x)}\]

is computably enumerable.

Question 3

Prove that the real number

\[\alpha_K=\sum_{k\in K}\frac{1}{(k+1)^2}\]

is lower semicomputable but not computable.

Question 4

Prove that a probability measure \(p\) on \(\set{0,1}^*\) is computable if and only if it is lower semicomputable.

Question 5

Prove that

\[P=\set{i: \lvert {dom \varphi_i} \rvert \leq 3}\]

is computably enforceably.