alt Hacker NewsThis reduction to the halting problem looks too handwawy to me. I don't see as a given that the possibility of the system taking into account the attack follows from the existence of the attack.
Replies
thfuran • today at 1:10 AM
And even if it is provably possible to do, that doesn't mean it's easy. That's kind of the basis of encryption.
They might be trying to talk about Rice's theorem?
https://en.wikipedia.org/wiki/Rice%27s_theorem
Formally, any non-trivial semantic property of a Turing machine is undecidable. Semantic here (roughly) means "behavioral" questions of the turing machine. E.g. if you only look at the "language" it defines (viewing it as a black box), then it is undecidable to answer any question about that language (including things like if it terminates on all inputs).
Practically though that isn't a complete no-go result. You can do various things, like
1. weaken the target you're looking for. if you're ok with admitting false positives or false negatives, Rice's theorem no longer applies, or 2. rephrase your question in terms of "syntatic properties", e.g. questions about how the code is implemented. Rust's borrow checker does this via lifetime annotations, for example.