I think there’s a fundamental asymmetry in the case you mentioned—it’s not verifying whether a program halts that’s difficult, it’s writing an algorithm that can verify whether any program halts. In other words, the problem is adversarial inputs. To keep the symmetry, we’d need to say that the generation problem is “generate all computer programs that halt,” which is also not possible.
I think a better example would be, how hard is it to generate a semiprime? Not hard at all: just generate 2 primes and multiply them. How hard is it to verify a number is semiprime? Very hard, you’d have to factor it.
I think there’s a fundamental asymmetry in the case you mentioned—it’s not verifying whether a program halts that’s difficult, it’s writing an algorithm that can verify whether any program halts. In other words, the problem is adversarial inputs. To keep the symmetry, we’d need to say that the generation problem is “generate all computer programs that halt,” which is also not possible.
I think a better example would be, how hard is it to generate a semiprime? Not hard at all: just generate 2 primes and multiply them. How hard is it to verify a number is semiprime? Very hard, you’d have to factor it.