Comment by pvillano

Deadlock is literally a halting problem.

We can't know for every possible program if it halts or not, but the complexity of programs we can determine is increasing as tools and techniques get better