非決定性 → 決定不能性 (第2刷 p.265)

[keigo.imai]

第2刷, 22章の最後の文章 (p.265):

どちらの証明も(無制限の)半単一化問題の非決定性(これ は Kfoury, Tiuryn, and Urzyczyn [260] が示した)に依存している。

翻訳で使った原著を確認したところ、 

both of these proofs depend on the undecidability of the (unrestricted) semi-unification problem, shown by Kfoury, Tiuryn, and Urzyczyn (1993b).

なので、 「非決定性」は「決定不能性」が正しそうです。