This is thorough and overall really well done, but after reading through Part 1, I can't help but trot out Brian Cantwell Smith's "The Limits of Correctness" https://www.student.cs.uwaterloo.ca/~cs492/11public_html/p18...
[1]: https://pron.github.io/posts/correctness-and-complexity