Decidability of Deadlock Detection

[Sherif Fadel]

I have a question on the decidability of deadlock detection. I heard a
speaker at one of the conferences I attended mention that the general
deadlock detection problem is Turing-undecidable. I was wondering about the
validity of this statement. I did some checking around and it seems that
*predicting* the occurrence of deadlock in the system, using e.g., static
analysis, is Turing-undecidable since it can be reduced to the Halting
problem. I was wondering whether it this is also true for the deadlock
detection problem. I know for a fact, from personal implementation, that it
is possible to design deadlock detection algorithms for reusable resources,
using cycle or knot detection in the general resource graph depending on the
resource request model. I also know that it is difficult to detect deadlock
for systems with only consumable resources (although it may be possible
using a claim-limited graph). I was wondering about the status of systems
with both consumable and reusable resources. Are they, in general,
Turing-undecidable? I apologize if this is not the appropriate forum for
this discussion. Thanks in advance.