Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable.

Does it make sense to discuss the complexity of computing a function that cannot be computed?

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a problem that is not computable in the model of computation you're talking about. Or, to put it the other way around, it only makes sense to talk about the computational complexity of the halting problem with respect to models of computation in which that problem is computable. For example, you could talk about the complexity of recursively enumerable problems using Turing machines with an oracle for the halting problem as your model of computation.

The proof you link to does not show that the halting problem is in NP. It shows that the halting problem is NP-hard, which just means that every problem in NP is polynomial-time reducible to the halting problem.

StackExchange Computer Science Q#89115, answer score: 22