Comment by xjm

Proving that a particular program terminates does not require deciding the halting problem on arbitrary programs (same for deadlock freedom)