Complexity of the halting problem
Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM_k$ halts on the empty tape.

In this case the string $s$ that lists the first $n$ bits $HALT(k)$, $k = 1,2,...,n$ is highly compressible:


$|s|=n$
let $h$ be the number of halting TMs between $1$ and $n$ ($h \leq n$)


If you know $h$, in order to build $s$ you can simply simulate all TMs between $1$ and $n$ and when $h$ of them stops you have enough information to reconstruct $s$ (you have the positions of the $1$s, the other can be set to $0$s).

So $K(s) = \lceil \log h \rceil + c$

If you interpret $HALT(k) = 1$ iif $TM_k$ halts on all inputs, then:

$K(s) =  min\{n, K(\lceil \log n \rceil, \lceil \log z \rceil )\} + c$

Where $z$ is the minimum number such that for every non halting $TM_k$ in 1..n exists $y \leq z$ such that $TM_k(y)$ doesn't halt. Informally you can simulate the $n$ TMs on inputs $1..z$ being sure that those who halts are the only TMs that always halts on all inputs.

Perhaps the same reasoning can be applied to points 2. and 3.