[j-pb]

The halting problem is RE complete, which means it's both RE Hard (every problem in RE can be reduced to the halting problem) and in RE.

It does seem from the article that they use an argument that the halting problem is unsolvable to somehow give an upper bound on complexity, but I wonder if the paper really does that.

"the fact that the halting problem is unsolvable" This is less of a fact and more of a conjecture. As always in mathematics we use implicit context and sometimes that context gets lost to a damaging degree. The whole, and true, sentence would be "the fact that the halting problem is unsolvable by a turing machine and, given that the Church Turing thesis is true, unsolvable in general".

It would be a pitty if the paper simply assumes the Church Turing thesis as true, because if we ever find a hypercomputation counterexample to the CTT, it'll probably come from a place like quantum computing and physics, where there might be more reals than the computable reals, where the axiom of choice could work, and where infinity might be a reified thing instead of a process.