[SCHiM]

I'm a not educated in mathematics, so I can't know for sure if what I'm going to respond to your question is really relevant or not. But here it goes anyway.

I'm a security researcher, and I write my own fuzzers. Fuzzers are tools that automatically search for inputs that have security implications for the program that you're testing. They algorithmically generate and mutate inputs, feed them to a program, and observe what happens, tens/hundreds/thousands of times a second.

If an input crashes a program you can think of this as "halting" the program. To have a fuzzer that could find any or all bugs in any program you run it on, in a feasible amount of time, would surely involve solving the halting problem I think. And sure, even after billions of tests, people still manage to find bugs in image decoders, so the fuzzers we do have are not flawless.

At the same time, I have experienced in the real world that fuzzers manage to penetrate unexpectedly deep into complex programs if given enough time. The validation on input performed by the target under test, the limited memory and storage in a modern PC sort of helps to keep your fuzzer on the rails. Unless cryptography is involved, which are like computational tar-pits for fuzzers. Any well guarded/specified program acts as its own guardrail against needing to solve the halting problem for the fuzzer.

It convinced me of the following, regarding the finding of security bugs in programs:

1) Fuzzers are good at targeting programs that perform rigorous input validation, barring cryptography.

2) You don't need a fuzzer for a program that does not perform rigorous input validation (where the fuzzer doesn't necessarily work well.)