"How does this proof/prove that ..."
Yes, your original is correct. The relative content clause in the middle may be leading to confusion. How does this proof (that the halting problem is undecidable) work?
The second is also grammatical if we take work to be a noun, but it doesn't mean what you intend. In fact, I have no idea what it might mean for a problem to be undecidable work.
How does this proof that the halting problem is undecidable work?
is correct. Alternatively use
How does this prove that the halting problem is undecidable?
It is wrong to write
How does this prove that the halting problem is undecidable work?
to mean what is intended. In the examples above, proof is a noun while prove is a verb.
Your sentence is grammatically correct but stylistically hard to understand. I recommend breaking it into two sentences. For instance:
This proof shows the halting problem is undecidable. How does this proof work?