In the general case you're right, it's equivalent to the halting problem. The outline of the proof by reduction: set up two communicating processes in a way tha

In the general case you're right, it's equivalent to the halting problem. The outline of the proof by reduction: set up two communicating processes in a way that will deadlock iff a particular loop in one process fails to terminate. So if you had a deadlock detector for arbitrary communicating processes, you could use turn it into a termination detector for arbitrary loops.