I've read this comment three times and I still can't figure out what you're trying to say. It sounds like you're arguing that all "puzzles" should exist on finite domains so that a brute force solution exists.

"(x, 2x, 4x) gives you a "yes" every time, therefore it is a correct answer, at least as automatically checkable."

Well, no: you can type 1, 2, 3 into the system and it will tell you "yes", but your rule says that it should tell you "no".

It is crucial to the definition of "correct answer" here that your rule should not just say "yes" only for tuples which the widget also says yes to, but also your rule should say "no" only for tuples which the widget also says no to. That is what the puzzle means when it's asking, "can you guess the rule that we've created?"

This makes it very, very different from what I think you're thinking about, which is situations where someone tells you, "what is the next number in this sequence? 4, 7, 13, 25, ...?" where technically there are an infinite number of rules which will generate those 4 numbers first and an arbitrary number afterwards. Technically one of them is "simplest" in the sense that it can be expressed in 7 symbols, but in general it's a complicated problem and there is no best solution.

"To find a 'no' you're reduced to random guessing. That's not a puzzle, that's crap."

In many ways it still is a puzzle but the space that it lives in is richer. If you think about typical "puzzles" they're things like: "here's a grid with some spaces filled in with numbers,

2 . . 2 . 2 .
. . . . . . .
1 . 3 . . 2 .
. . . . . . .
3 . . . 2 . 3
. . 2 . . . .
. . . . . . .

Each number is a block in a block wall. We want you to turn this into a block maze so that each 'block wall' (set of blocks connected by adjacency) contains exactly one numbered-block whose number says how many total blocks are in the wall. Furthermore the path (non-block space) of the block maze should be connected and should not contain any 'rooms' -- that is, any 2x2 or larger segments of open space."

This 7x7 grid has 10 spaces which are known to be blocks and exactly 12 more blocks scattered in the remaining 39 spaces, so just by those factors alone we're searching only (39 choose 12) ~= 3.91 billion possibilities; we can also use a quick heuristic to identify 6 places which must be "space" to break apart adjacent numbered walls, removing 91% of that search space.

The puzzles, "I have a set of integers where inclusion in the set is governed by a short rule, you can ask me any integer and I will tell you whether it is in my set", by contrast, have an infinite search space. This means that any solution is going to be more interesting, as will the means for checking that solution's validity. You could require, for instance, a Haskell expression of 140 characters or fewer which turns a nonnegative Int named `n` into a Bool, to be judged as "valid" or "invalid" if it properly filters `[1..10000000] :: [Int]`. You could even give the first 100 numbers in the set, e.g.:

ghci> take 100 $ filter trueFn [0..]
[2,5,8,9,13,14,18,19,20,25,26,27,32,33,34,35,41,42,43,44,50,51,52,53,54,61,62,63,64,65,
72,73,74,75,76,77,85,86,87,88,89,90,98,99,100,101,102,103,104,113,114,115,116,117,118,
119,128,129,130,131,132,133,134,135,145,146,147,148,149,150,151,152,162,163,164,165,
166,167,168,169,170,181,182,183,184,185,186,187,188,189,200,201,202,203,204,205,206,
207,208,209]

In this case that's pretty much enough to see the general pattern; the verification covers 10 million bits while the 140-character limit probably limits your search space to 1000 bits or so, so it's going to be hard to get an "incorrect" answer which agrees on that subspace of the whole.