tl;dr- The answer depends on exactly what requirements you impose on the question.
If you merely want to detect all viruses without further constraint, then simply flag anything and everything as a virus, and you're done.
If you want to properly identify all programs as either a virus or not, then it's impossible in the unbound case since the classification problem reduces to the halting problem.
If you want to properly identify all programs as either a virus or not, and you're considering a finite machine, then it's theoretically possible but not generally feasible in practice.
If you allow that the computer can produce random errors, then any program can be a virus.
Case 1: Complete virus detection
Obviously, flagging all programs as viruses catches 'em all. (Pok'e'mon!)
Starting with this case to make the point that it's not hard to detect all viruses; rather, the specific theoretical problem is correctly classifying iff programs are viruses.
Case 2: Impossible to correctly classify in a general, unbounded scenario
Consider the program:
doHaltingProblem(); // Not a virus operation itself
installEveryVirusEver(); // Definitely a virus operation, but will it happen?
In this case, the program is a virus only if the halting problem halts, allowing
installEveryVirusEver() to occur. So, virus-detection reduces to the halting problem in the general, unbound case.
Case 3: Possible by brute-force search in bounded scenarios
If programs to be classified as viruses-or-not are to operate on a finite machine, then you can simply simulate the machine running from every possible starting state. Finite machines will eventually loop back to a prior state, so it's necessarily a finite (if lengthy) analysis.
Case 4: Machines that can error can have viruses spontaneously emerge
Assuming that a machine can run a program that'd be considered a virus, and there's a non-zero chance of a random mutation shifting it into that state, then it should eventually arrive at a virus state.
Which is kind of a boring point, but just for completeness's sake.
Discussion on the quote in the question
Viruses have no “cure.” It’s been mathematically proven that it is always possible to write a virus that any existing antivirus program can’t stop.
–"Secrets & Lies", Bruce Schneier, page 154
As pointed out in Case (1) above, it's possible to flag all viruses by just flagging everything as a virus; that's easy. What's impossible is to, in an unbound case, determine if every possible program is a virus or not.
Further, it's difficult to establish if particular programs are viruses in bound cases. For example, consider the program:
var toExecute = decryptByBruteForce([ciphertext]); // Decrypt the next part of the program by brute-force
run(toExecute); // Run the now-decrypted part of the program
As discussed in Case (3), this program can be classified as a virus-or-not when run on a finite machine, but since doing so would require brute-forcing an encrypted message, it's not likely feasible in practical scenarios.
So, in real-world applications, it reduces to an issue of heuristics: anti-virus programs make guesses at what's a virus or not. Or if you want more reliable security, you could have an anti-virus program flag anything that it can't prove to be safe, dodging the issue of needing to classify every possible program.
Unfortunately, the use of heuristics gives knowledgable attackers security holes to target. Without reading the source of the quote, I suspect that this problem is what they were trying to refer to.