The halting problem states that “is there a computer program that can look at the code of any other program and decide if that other program will ever stop running?”; it is provably unsolvable.

Why does this problem matter? By “halt” we mean fulfill a condition such as saying if something is true or not, such as “is this program a virus”? In the 1980s that’s exactly what Fred Cohen did - he posed the question about whether there was such a thing as an undetectable computer virus. His analysis reduces (converts to another form) his question to the halting problem. The technique of reduction (in both computing and math) is powerful in that if you can determine one problem to be the same as another, then any solution (or lack of solution) for one problem applies equally to the other. The halting problem itself can be reduced to much older and deeper mathematical theorems.

You’re probably not surprised that some computer viruses go undetected and would likely think that an issue of your anti-virus (or other defenses) needing a “signature update”. Right there that’s an indicator of the problem, signature updates are a specific way to work around the undecidability of detecting all computer viruses, you give the virus detection program additional input. If there was a general algorithm that could detect the set of all possible computer viruses then signatures would not be required.

If the halting problem means we can’t create an algorithm that could detect the set of all possible computer viruses then by extension we can’t create an algorithm that could detect the set of all possible malicious backdoor code.

Given that these are not computable problems, neither quantum computing nor AI will solve this issue either.